0%

刷算法(7)-三数之和

15. 三数之和

给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。注意:答案中不可以包含重复的三元组。

解法

屏幕快照 2019-10-01 下午3.51.47.png

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
26
public List<List<Integer>> threeSum(int[] nums) {

List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++){
if (nums[i] > 0) break;
if (i > 0 && nums[i] == nums[i-1]) continue;
int left = i+1, right = nums.length - 1;
while (left < right){
int sum = nums[i] + nums[left] + nums[right];
if ( sum == 0){
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
while (left < right && nums[right] == nums[right-1]) right--;
while (left < right && nums[left] == nums[left+1]) left++;
left++;
right--;
}else if (sum > 0){
right--;
}else{
left++;
}
}
}

return result;
}

心得

  1. 整体思路是先对数组进行排序,然后对有序数组依次查找,用最左、最右两个指针索引进行遍历;
  2. 因为数组是递增的,一旦num[i] > 0则对索引i就不需要再找了需要结束整个流程(因为i右边的数都比它大);
  3. 如果遍历到i,但是num[i]等于num[i-1],则忽略这个i,从i的下一个开始找,通过for循环控制;
  4. 针对i,定义left和right,在left和right区间去找,计算三者sum;
  5. 如果sum = 0,则放到结果里,同时对left和right,判断是否有重复的,如果有重复的就往前/往后移位。这里有两个注意事项:
  • 1)注意是通过left和left+1比的,意味着出while后,left指的位置仍然是当下参与计算sum的那个索引,出循环后left和right要进行递增、递减操作,这一切都归功于数组是递增有序的;
  • 2)注意while循环的条件一定有left < right,这一点非常关键;
  1. 如果sum > 0意味着值太大了,需要小点,那就把right递减下;
  2. 如果sum < 0意味着太小了,需要更大,那就把left递增加大下这个值,因为right是从最右边来的,已经是最大的了;

参考