两数之和（Two Sum）——梦开始的地方
题目链接：1. 两数之和
这就是单词表里的Abandon Abort一类的存在，helfront world新手体验局，没啥好说的，我也没啥新颖的解法，遍历元素然后HashMap查表匹配target - nums[i]就好了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
int[] res = new int[2];
for(int i = 0; i < nums.length; i++) {
if(map.containsKey(target - nums[i])) {
res[0] = map.get(target - nums[i]);
res[1] = i;
return res;
}
else {
map.put(nums[i], i);
}
}
return res;
}
}
|
三数之和（Three Sum）
题目链接：15. 三数之和
题目是说需要把给出的list里相加为0的三元组找出来。一开始除了根本ac不了的暴力解法想不到什么思路，就大概参考一下热度比较高的思路。
双指针法
双指针法的原理是在已排序的数组内使用一头一尾两个指针向中间移动以找到两数之和等于指定值的全部组合。（所以啊，这也可以解决第一个问题）本题为三数之和，可以在排序的数组中先固定一个数（从前向后遍历），将这个数字的相反数作为target，实现以这个数字之后的list为范围的双指针两数之和问题。具体来说也就是两个步骤：
- 排序。这个可以不用费时间了（之后应该会再总结一遍各种排序算法，虽然已经被大家讲烂了，但对于我来说好记性不如烂笔头），直接调库
Arrays.sort(num)就好了。给自己多啰嗦一句，Array的排序底层实现是混合的，对于length() < 47的列表直接使用插入排序，大于这个长度的使用双轴快排。
- 遍历数组和双指针算法。需要注意的是，我们操作三个元素，分别为遍历的时候固定的元素、双指针的头指针元素和尾指针元素，对于这三个元素而言在其移动方向上如果有前后重复都应该排除掉，否则就有可能出现重复的三元组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public List<List<Integer>> threeSum(int[] num) {
Arrays.sort(num);
List<List<Integer>> res = new ArrayList<>();
for(int i = 0; i < num.length-2; ++i){
if(i > 0 && num[i] == num[i-1]) continue;
int front = i+1, rear = num.length-1, sum = 0 - num[i];
while (front < rear) {
if (num[front] + num[rear] == sum) {
res.add(Arrays.asList(num[i], num[front], num[rear]));
while (front < rear && num[front] == num[front+1]){
front++;
}
while (front < rear && num[rear] == num[rear-1]) {
rear--;
}
front++;
rear--;
} else if (num[front] + num[rear] < sum) front++;
else rear--;
}
}
return res;
}
}
|
除此之外好像还有更优的解法，一刷暂时先不管那么多，先把通用方法记牢了再说吧。
