LeetCode第[1]题(Java):Two Sum 标签:Array

时间:2023-03-08 15:06:55
LeetCode第[1]题(Java):Two Sum   标签:Array

题目:

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

翻译:

给定一组整数,两个数字的返回索引,它们的和会等于一个特定的数。

您可能假设每个输入都有一个解决方案,但是你不能使用同一个元素两次。(好吧一开始英语弱鸡的我也没懂,后来编程的时候想到的解释:同一个数不能通过自加而得到目标数)

第一遍编写:74ms

class Solution {
public int[] twoSum(int[] nums, int target) {
Set<Integer> resultSet = new HashSet<Integer>();
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) { // 就是这里想到一个数自加,所以应该从i+1开始。
if (nums[i] + nums[j] == target) {
resultSet.add(i);
resultSet.add(j);
}
}
}
int[] result = new int[resultSet.size()];
for (int i = 0; i < result.length; i++) {
result[i] = (Integer) resultSet.toArray()[i];
}
return result;
}
}

好吧,第一次刷题,隐隐小激动,一开始确实没看清题目。。

看清题目后第一次:46ms    时间复杂度:O(n2)

 class Solution {
public int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
result[0] = i;
result[1] = j;
break;
}
}
}
return result;
}
}

自己看着都觉得菜的很。。竟然用了嵌套for。。

下面是参考答案:12ms    时间复杂度:O(n)

     public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
int[] result = new int[2]; for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) {
result[0] = map.get(target - nums[i]);
result[1] = i; // 此时 i 对应的元素还没有放进去。
return result;
}
map.put(nums[i], i);
}
return result;
}

原来用了HashMap来定位两者有某种关系的数。。快了一倍多。。

结论:

当需要使用嵌套for循环来查找或者定位的时候,尽量优先考虑是否能使用Map(存储每一个值作为key,相应下标作为value)

使用  map.containsKey(__) 方法来进行定位

2018-1-8更新:今天做到3sum想到和这里的2sum联系,

3sum:求所有的相加为目标值的数组,

2sum:一旦查找到相加为目标值的俩数组则直接返回俩下标,程序直接结束(仅一组)

现在将2sum的题目改为如下:

给定一个n个整数的数组,在数组中找到和为目标值的所有唯一的两个元素组合【注意不是求下标】

注意:答案集不能包含重复的双胞胎。

测试用例:{1,4,-1,2,-1,0}   1     结果:[[0, 1], [-1, 2]]

     {3,2,3,4,1,4,5,5}  8     结果:[[4, 4], [3, 5]]

Code1:时间复杂度:O(N)    【其实应该是Arrays.sort(num)的复杂度】

     public static List<List<Integer>> twoSumAll(int[] num, int target) {
Arrays.sort(num); // 将所有相同元素挨在一起
List<List<Integer>> res = new LinkedList<List<Integer>>();
Set<Integer> set = new HashSet<Integer>(); // 不需要下标,并且需要元素唯一,所以采用Set
for (int i = 0; i < num.length; i++) {
if (set.contains(target - num[i])) {
res.add(Arrays.asList(target - num[i], num[i]));
set.remove(target - num[i]); // 防止后续重复元素继续利用此值(因为已经排序,后面不会再有前面的值,不需要再remove(num[i]))
}
set.add(num[i]);
}
return res;
}

此方法仍然采用上面2sum的思想,利用contains()函数减少一次循环,注意Set的remove使答案避免了”双胞胎数组“

下面采用第15题的3sum的‘’双指针相向移动‘’的思想进行算法编写:

Code2:时间复杂度:O(N)   【其实应该是Arrays.sort(num)的复杂度】

     public static List<List<Integer>> twoSumAll2(int[] num, int target) {
Arrays.sort(num);
List<List<Integer>> res = new LinkedList<List<Integer>>();
int left = 0;
int right = num.length - 1;
while (left < right) {
if (num[left] + num[right] == target) {
res.add(Arrays.asList(num[left], num[right]));
while (left < right && num[left] == num[left+1]) left++;
while (left < right && num[right] == num[right-1]) right--;
left++;
right--;
} else if (num[left] + num[right] < target) {
left++;
} else {
right--;
}
}
return res;
}

双指针相向移动:利用了  已排序数组  和  所查找的两个数的和为定值  这两个性质

        这两个性质如果联合一起用的话………………duang!!!

        在已排序数组两端指针所指数之和如果小于目标值,只需要移动左边的指针,否则只需要移动右边的指针

        【还看不懂可以自己打草稿试试,或者看我这个博客:LeetCode第[15]题(Java):3Sum 标签:Array

结论:在求和为目标数时,求下标——HashMap;

            求具体组合值——前后指针;