当前位置：首页 > ds >正文

【力扣】第15题：三数之和

ds 2025/7/25 20:34:01

原文链接：15. 三数之和 - 力扣（LeetCode）

思路解析

双指针：

（1）头尾指针对应值相加如果大于目标值(target)，那么只能尾指针-1；如果小于target，那么只能头指针+1。

（2）如何去除重复？因为已经排好序了，如果下一个要检索的值等于前一个检索的值，直接跳过。

    public List<List<Integer>> threeSum(int[] nums) {/*** 双指针：* 头指针：开始指向当前元素的下一个元素* 尾指针：开始指向最后一个元素*/Arrays.sort(nums);int len = nums.length;List<List<Integer>> ans = new ArrayList<>();for (int i = 0; i < nums.length; i++) {if (i > 0 && nums[i] == nums[i - 1]) continue;int j = i + 1;int k = len - 1;int x = nums[i];while(j<k){int result = x+nums[j]+nums[k];if(result>0){k--;}else if(result<0){j++;}else {ans.add(Arrays.asList(x,nums[j],nums[k]));j++;//继续排查当前遍历的i，还有没有别的组合while(nums[j]==nums[j-1] && j<k){j++;}k--;while(nums[k]==nums[k+1] && j<k){k--;}}}}return ans;}

两个优化：

优化1：如果最小的三个值相加都大于0，那么没有满足要求的，直接break

优化2：如果当前值和最大的两个值相加都小于0，那么本次遍历的i没有满足要求的，直接continue

    public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);int len = nums.length;List<List<Integer>> ans = new ArrayList<>();for (int i = 0; i < nums.length; i++) {if (i > 0 && nums[i] == nums[i - 1]) continue;int j = i + 1;int k = len - 1;int x = nums[i];if(x+nums[j]+nums[j+1] > 0) break;//优化1if(x+nums[k]+nums[k-1] < 0) continue;//优化2while(j<k){int result = x+nums[j]+nums[k];if(result>0){k--;}else if(result<0){j++;}else {ans.add(Arrays.asList(x,nums[j],nums[k]));j++;//继续排查当前遍历的i，还有没有别的组合while(nums[j]==nums[j-1] && j<k){j++;}k--;while(nums[k]==nums[k+1] && j<k){k--;}}}}return ans;}

同样的思路，会做这一题，你就会两数之和了，两数之和也是用这个思想，更简单