三数之和（medium）07

用户11319080

发布于 2024-10-17 19:27:42

8500

代码可运行

文章被收录于专栏：学习学习

运行总次数：0

代码可运行

题目：三数之和第一种解法：暴力枚举（省略代码）

第二种解法：排序+双指针+单调性

这道题算法运用了06那道题的一部分算法。我写的代码

 public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> lists=new ArrayList<>();
        Arrays.sort(nums);
        for (int cur= 0; cur < nums.length-2; ) {
            if(nums[cur] > 0) break;
            int left=cur+1;
            int right=nums.length-1;
            int key=- nums[cur];
            while(left<right) {
                if (nums[left]+ nums[right]> key) {
                    right--;
                } else if(nums[left]+ nums[right]< key) {
                    left++;

                } else {
                    List<Integer> intNums=new ArrayList<>();
                    intNums.add(nums[left]);
                    intNums.add(nums[right]);
                    intNums.add(nums[cur]);
                    lists.add(intNums);
                    right--;
                    left++;
                    while(right>left&&nums[right]==nums[right+1]) {
                        right--;
                    }
                    while(left<right&&nums[left]==nums[left-1]) {
                        left++;
                    }
                }

            }
            cur++;
            while(cur<nums.length-2&&nums[cur]==nums[cur-1]) {
                cur++;
            }
        }
        return lists;
    }

官方：

class Solution
{
    public List<List<Integer>> threeSum(int[] nums)
    {
        List<List<Integer>> ret = new ArrayList<>();
        // 1. 排序
        Arrays.sort(nums);
        // 2. 利⽤双指针解决问题
        int n = nums.length;
        for(int i = 0; i < n; ) // 固定数 a
        {
            if(nums[i] > 0) break; // ⼩优化
            int left = i + 1, right = n - 1, target = -nums[i];
            while(left < right)
            {
                int sum = nums[left] + nums[right];
                if(sum > target) right--;
                else if(sum < target) left++;
                else
                {
                    // nums[i] nums[left] num[right]
                    ret.add(new ArrayList<Integer>(Arrays.asList(nums[i],
                            nums[left], nums[right])));
                    left++; right--; // 缩⼩区间继续寻找
                    // 去重：left right
                    while(left < right && nums[left] == nums[left - 1]) left++;
                    while(left < right && nums[right] == nums[right + 1])
                        right--;
                }
            }
            // 去重：i
            i++;
            while(i < n && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }
}

这里我根据官方可以优化我们的代码：比如比较两数和时候，提前定义一个sum，这样后面就直接用sum代替和，代码长度就会减少许多。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-10-17，如有侵权请联系 cloudcommunity@tencent.com 删除

排序