聖地亞歌

Leetcode P0015"3Sum" 题解

2020/08/18 Leetcode

博文中会简要介绍Leetcode P0015题目分析及解题思路。

“3Sum”是一道非常经典的题目，这道题可以划归为”kSum”这样的原型。这道题考察的核心是双指针和指针移动的边界条件。

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

这道题最直接的思路是暴力解法，将数组排序后可以保证对结果去重，直接三层循环分别固定left指针，med指针然后移动right指针。这样的解法的时间复杂度是O(n^3)。

但这道题有个明显的优化。我们不难发现，对数组排序后，在固定left指针后，med指针和right指针其实可以是一个类似p0011题目的双指针相向移动的问题。那么解决这样一个双指针相向移动的问题，关键在于确立双指针移动的边界条件，即什么时候该移动？该移动哪个指针？

显然，可以得出以下边界条件：

    sum3 = nums[left]+nums[med]+nums[right]

    fix left;
    if sum3 > target
        move right; right指针指向的是最大值，由于数组排序，right右边的一定更大，所以左移
    else if sum3 < target
        move med; 理由同上但相反
    else
        record;

        move left;
        move right; 这两个指针的相向移动是思路的核心，要强调，移动不能交错，移动需要保证结果去重
    
    move left;

类似的这类题目，其实都是双指针题目的衍生。这道题其实有三个指针，但是通过固定一个指针，我们将这道题转化为了双指针问题。多指针（>2）问题往往很难确立合适的指针移动条件，很容易会陷入复杂条件导致错误的解题方法。遇到多指针问题，首先想到的应该是化繁为简，将多指针降维成双指针问题来解决。

以下是Java的题解代码实现。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        if (nums == null || nums.length < 3)
            return new ArrayList<>();
        
        int target = 0;
        List<List<Integer>> triplets = new ArrayList<>();
        
        Arrays.sort(nums);
        for (int left=0; left<nums.length-2; ++left) {
            if (left > 0 && nums[left] == nums[left-1])
                continue;
            
            int med = left+1, right = nums.length-1;
            while (med < right) {
                int sum3 = nums[left]+nums[med]+nums[right];
                
                if (sum3 < target)
                    ++med;
                else if (sum3 > target)
                    --right;
                else {
                    triplets.add(Arrays.asList(new Integer[] {nums[left], nums[med], nums[right]}));
                    
                    ++med;
                    while (med < right && nums[med] == nums[med-1])
                        ++med;
                    
                    --right;
                    while (right > med && nums[right] == nums[right+1])
                        --right;
                }
            }
        }
        
        return triplets;
    }
}

以下是C++的题解代码实现。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        if (nums.size() < 3) 
            return vector<vector<int>>();
        
        sort(nums.begin(), nums.end());
        int target = 0;
        vector<vector<int>> triplets;
        for (int left=0; left<nums.size()-2; ++left) {
            if (left > 0 && nums[left] == nums[left-1])
                continue;
            
            int med = left+1, right = nums.size()-1;
            while (med < right) {
                int sum3 = nums[left]+nums[med]+nums[right];
                
                if (sum3 > target)
                    --right;
                else if (sum3 < target)
                    ++med;
                else {
                    triplets.push_back({nums[left], nums[med], nums[right]});
                    
                    ++med;
                    while (med < right && nums[med] == nums[med-1])
                        ++med;
                    
                    --right;
                    while (right > med && nums[right] == nums[right+1])
                        --right;
                }
            }
            
        }
        
        return triplets;
    }
};

Search

    Table of Contents