LeetCode 两数之和
给定一个整数数组，返回两个数字的索引，使它们相加到特定目标。
您可以假设每个输入只有一个解决方案，并且您可能不会两次使用相同的元素。
方法一
public List<String> twoSum2(int[] arr, int sum) {
if (arr == null || arr.length == 0) {
return new ArrayList<>();
}
List<String> list = new ArrayList<>();
for (int i = 0; i < arr.length - 1; i++) {
for (int j = i + 1; j < arr.length - 1; j++) {
if (arr[i] + arr[j] == sum) {
// 这里记录的是数组值 也可以记录下标 这里只是为了方便查看结果
list.add(arr[i] + "," + arr[j]);
}
}
}
return list;
}
| 时间复杂度 | O(n^2) |
| 空间复杂度 | O(1) |
方法二
public List<String> twoSum(int[] arr, int sum) {
if (arr == null || arr.length == 0) {
return new ArrayList<>();
}
List<String> st = new ArrayList<>();
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
// 查看数组中是否存在当前值和目标值差的值
if (map.containsKey(sum - arr[i])) {
st.add(map.get(sum - arr[i]) + "," + arr[i]);
} else {
// 记录下元素值
map.put(arr[i], arr[i]);
}
}
return st;
}
public List<String> sum2(int[] nums, int target) {
if (nums == null || nums.length <= 0) {
return null;
}
List<String> results = new ArrayList<>();
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
// 检验当前值是否存在于存储的之差中
Integer value = map.get(nums[i]);
if (value != null) {
results.add(nums[value] + "," + nums[i]);
}
// 记录目标值和当前值差
map.put(target - nums[i], i);
}
return results;
}
此方法增加一个空间复杂度，记录的方式可能有多种 都能达到目的,速度优于第一种
| 时间复杂度 | O(n) |
| 空间复杂度 | O(n) |