15. 3Sum

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.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Example 2:

Input: nums = []
Output: []

Example 3:

Input: nums = [0]
Output: []

大小排序後依總和決定要加或減。

Java

Time: O(nˆ2), Space: O(n)

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums); // O(nlogn)
        List<List<Integer>> res = new LinkedList<>(); 
        for (int i = 0; i < nums.length-2; i++) { // O(n)
            if (i == 0 || (i > 0 && nums[i] != nums[i - 1])) {
                int j = i + 1, k = nums.length - 1, target = 0 - nums[i];
                while (j < k) { O(n)  
                    if (nums[j] + nums[k] == target) {
                        res.add(Arrays.asList(nums[i], nums[j], nums[k]));
                        while (j < k && nums[j] == nums[j + 1]) j++;
                        while (j < k && nums[k] == nums[k - 1]) k--;
                        j++; k--;
                    } else if (nums[j] + nums[k] < target) ++j;
                    else --k;
               }
            }
        }
        return res;
    }
}

Python

Time: O(nˆ2), Space: O(n)

from typing import List
class Solution(object):      
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort() # 小到大排序
        added = set()
        out = []
        for i in range(len(nums) - 1, -1, -1):
            last = nums[i]
            start, end = 0, i - 1
            while start < end:
                s = last + nums[start] + nums[end] # 加總
                if s == 0:
                    if (last, nums[start], nums[end]) not in added:  # 紀錄沒看過的合法組合
                        out.append([last, nums[start], nums[end]])
                    added.add((last, nums[start], nums[end]))
                    start += 1 # 持續加到結束
                elif s > 0: # 總和過多
                    end -= 1
                else: start += 1 # 總和過少
        return out

---

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)