Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/15.html

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

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]]
Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

 

Constraints:

  • 3 <= nums.length <= 3000
  • -105 <= nums[i] <= 105

Algorithm

Sort the original array in ascending order and then traverse the sorted array.

Note that the traversal is not up to the last element, but to the third last element from the end. To optimize the algorithm, we can perform a pruning operation by breaking the traversal when a positive number is encountered. Since the array is sorted, if the first number to be fixed is positive, then the following numbers, if they are all positive, will never sum up to zero.

Additionally, we add a process to skip repeated numbers. Starting with the second number, if it is equal to the previous number, skip it because we don’t want to fix the same number twice.

For each number in the traversal, subtract it from 0 to get the target. Then, we only need to find two numbers whose sum is equal to the target. We can use two pointers to point to the first and last two numbers of the array, starting after the fixed number.

  • If the sum of the two numbers is equal to the target, then the two numbers and the fixed number are stored in the result. Next, we skip the step of repeating numbers. Both pointers need to detect repeated numbers.
  • If the sum of the two numbers is less than the target, move the pointer i to the right to increase the number pointed to.
  • Similarly, if the sum of the two numbers is greater than the target, move the pointer j to the left to reduce the number pointed to.

Code

  • public class Three_Sum {
    	public static void main(String[] args) {
    	    List<List<Integer>> list = new ArrayList<>();
    	    int[] a = new int[]{3,2,1};
    
    	    Arrays.sort(a);
    	    System.out.println(a[0]);
    	}
    
        // time: O(N)
        // space: O(1)
    	public class Solution {
    
    	    List<List<Integer>> list = new ArrayList<>();
    
    	    public List<List<Integer>> threeSum(int[] nums) {
    
    	        if(nums.length < 3) {
    	            return list;
    	        }
    
    	        Arrays.sort(nums);
    
    	        // hold one pointer, other two pointer moving
    	        for(int ancher = 0; ancher < nums.length; ancher++) {
    
    	            if(ancher > 0 && nums[ancher] == nums[ancher - 1]) {
    	                continue;
                    }
    
    	            int i = ancher + 1;
    	            int j = nums.length -1;
    
    	            while(i < j) {
    
    	                if(nums[ancher] + nums[i] + nums[j] == 0) {
    
    	                    // @note: Arrays.asList()
    	                    list.add(Arrays.asList(nums[ancher], nums[i], nums[j]));
    
    	                    i++;
    	                    j--;
    
    	                    // @note: optimization. above i,j is updated already, compare with previous position
    	                    while(i < j && nums[i] == nums[i - 1]) {
    	                        i++;
    	                    }
    	                    while(j > i && nums[j] == nums[j + 1]) {
    	                        j--;
    	                    }
    
    	                } else if(nums[ancher] + nums[i] + nums[j] < 0) {
    	                    i++;
    
    	                    // @note: same here, possibly updated already, note i-1 or i+1
    	                    while(i < j && nums[i] == nums[i - 1]) {
    	                        i++;
    	                    }
    	                } else {
    	                    j--;
    
    	                    // @note: same here, possibly updated already, note i-1 or i+1
    	                    while(j > i && j + 1 < nums.length && nums[j] == nums[j + 1]) {
    	                        j--;
    	                    }
    	                }
                    }
    
    	        }
    
    	        return list;
    	    }
    	}
    
    }
    
    
    ############
    
    class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            Arrays.sort(nums);
            List<List<Integer>> ans = new ArrayList<>();
            int n = nums.length;
            for (int i = 0; i < n - 2 && nums[i] <= 0; ++i) {
                if (i > 0 && nums[i] == nums[i - 1]) {
                    continue;
                }
                int j = i + 1, k = n - 1;
                while (j < k) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        ans.add(Arrays.asList(nums[i], nums[j++], nums[k--]));
                        while (j < n && nums[j] == nums[j - 1]) {
                            ++j;
                        }
                        while (k > j && nums[k] == nums[k + 1]) {
                            --k;
                        }
                    } else if (nums[i] + nums[j] + nums[k] < 0) {
                        ++j;
                    } else {
                        --k;
                    }
                }
            }
            return ans;
        }
    }
    
  • // OJ: https://leetcode.com/problems/3sum/
    // Time: O(N^2)
    // Space: O(1)
    class Solution {
    public:
        vector<vector<int>> threeSum(vector<int>& A) {
            sort(begin(A), end(A));
            vector<vector<int>> ans;
            int N = A.size();
            for (int i = 0; i < N - 2; ++i) {
                if (i && A[i] == A[i - 1]) continue;
                int L = i + 1, R = N - 1;
                while (L < R) {
                    int sum = A[i] + A[L] + A[R];
                    if (sum == 0) ans.push_back({ A[i], A[L], A[R] });
                    if (sum >= 0) {
                        --R;
                        while (L < R && A[R] == A[R + 1]) --R;
                    }
                    if (sum <= 0) {
                        ++L;
                        while (L < R && A[L] == A[L - 1]) ++L;
                    }
                }
            }
            return ans;
        }
    };
    
  • class Solution:
        def threeSum(self, nums: List[int]) -> List[List[int]]:
            nums.sort()
            n = len(nums)
            ans = []
            for i in range(n - 2):
                if nums[i] > 0:
                    break
                if i and nums[i] == nums[i - 1]:
                    continue
                j, k = i + 1, n - 1
                while j < k:
                    if nums[i] + nums[j] + nums[k] == 0:
                        ans.append([nums[i], nums[j], nums[k]])
                        j, k = j + 1, k - 1
                        while j < n and nums[j] == nums[j - 1]:
                            j += 1
                        while k > j and nums[k] == nums[k + 1]:
                            k -= 1
                    elif nums[i] + nums[j] + nums[k] < 0:
                        j += 1
                    else:
                        k -= 1
            return ans
    
    ############
    
    class Solution(object):
      def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        nums.sort()
        for i in range(0, len(nums)):
          if i > 0 and nums[i] == nums[i - 1]:
            continue
          target = 0 - nums[i]
          start, end = i + 1, len(nums) - 1
          while start < end:
            if nums[start] + nums[end] > target:
              end -= 1
            elif nums[start] + nums[end] < target:
              start += 1
            else:
              res.append((nums[i], nums[start], nums[end]))
              end -= 1
              start += 1
              while start < end and nums[end] == nums[end + 1]:
                end -= 1
              while start < end and nums[start] == nums[start - 1]:
                start += 1
        return res
    
    
  • func threeSum(nums []int) (ans [][]int) {
    	sort.Ints(nums)
    	n := len(nums)
    	for i := 0; i < n-2 && nums[i] <= 0; i++ {
    		if i > 0 && nums[i] == nums[i-1] {
    			continue
    		}
    		j, k := i+1, n-1
    		for j < k {
    			if nums[i]+nums[j]+nums[k] == 0 {
    				ans = append(ans, []int{nums[i], nums[j], nums[k]})
    				j, k = j+1, k-1
    				for j < k && nums[j] == nums[j-1] {
    					j++
    				}
    				for j < k && nums[k] == nums[k+1] {
    					k--
    				}
    			} else if nums[i]+nums[j]+nums[k] < 0 {
    				j++
    			} else {
    				k--
    			}
    		}
    	}
    	return
    }
    
  • function threeSum(nums: number[]): number[][] {
        nums.sort((a, b) => a - b);
        const ans = [];
        const n = nums.length;
        for (let i = 0; i < n - 2 && nums[i] <= 0; i++) {
            const target = 0 - nums[i];
            let l = i + 1;
            let r = n - 1;
            while (l < r) {
                if (nums[l] + nums[r] === target) {
                    ans.push([nums[i], nums[l++], nums[r--]]);
                    while (nums[l] === nums[l - 1]) {
                        l++;
                    }
                    while (nums[r] === nums[r + 1]) {
                        r--;
                    }
                } else if (nums[l] + nums[r] < target) {
                    l++;
                } else {
                    r--;
                }
            }
            while (nums[i] === nums[i + 1]) {
                i++;
            }
        }
        return ans;
    }
    
    
  • /**
     * @param {number[]} nums
     * @return {number[][]}
     */
    var threeSum = function (nums) {
        const n = nums.length;
        let res = [];
        nums.sort((a, b) => a - b);
        for (let i = 0; i < n - 2 && nums[i] <= 0; ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            let j = i + 1;
            let k = n - 1;
            while (j < k) {
                if (nums[i] + nums[j] + nums[k] === 0) {
                    res.push([nums[i], nums[j++], nums[k--]]);
                    while (nums[j] === nums[j - 1]) ++j;
                    while (nums[k] === nums[k + 1]) --k;
                } else if (nums[i] + nums[j] + nums[k] < 0) {
                    ++j;
                } else {
                    --k;
                }
            }
        }
        return res;
    };
    
    
  • # @param {Integer[]} nums
    # @return {Integer[][]}
    def three_sum(nums)
      res = []
      nums.sort!
    
      for i in 0..(nums.length - 3)
        next if i > 0 && nums[i - 1] == nums[i]
        j = i + 1
        k = nums.length - 1
        while j < k do
          sum = nums[i] + nums[j] + nums[k]
          if sum < 0
            j += 1
          elsif sum > 0
            k -= 1
          else
            res += [[nums[i], nums[j], nums[k]]]
            j += 1
            k -= 1
            j += 1 while nums[j] == nums[j - 1]
            k -= 1 while nums[k] == nums[k + 1]
          end
        end
      end
    
      res
    end
    
    
  • public class Solution {
        public IList<IList<int>> ThreeSum(int[] nums) {
            Array.Sort(nums);
            int n = nums.Length;
            IList<IList<int>> ans = new List<IList<int>>();
            for (int i = 0; i < n - 2 && nums[i] <= 0; ++i) {
                if (i > 0 && nums[i] == nums[i - 1]) {
                    continue;
                }
                int j = i + 1, k = n - 1;
                while (j < k) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        ans.Add(new List<int> { nums[i], nums[j++], nums[k--] });
                        while (j < n && nums[j] == nums[j - 1]) {
                            ++j;
                        }
                        while (k > j && nums[k] == nums[k + 1]) {
                            --k;
                        }
                    } else if (nums[i] + nums[j] + nums[k] < 0) {
                        ++j;
                    } else {
                        --k;
                    }
                }
            }
            return ans;
        }
    }
    
  • use std::cmp::Ordering;
    
    impl Solution {
        pub fn three_sum(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
            nums.sort();
            let n = nums.len();
            let mut res = vec![];
            let mut i = 0;
            while i < n - 2 && nums[i] <= 0 {
                let mut l = i + 1;
                let mut r = n - 1;
                while l < r {
                    match (nums[i] + nums[l] + nums[r]).cmp(&0) {
                        Ordering::Less => l += 1,
                        Ordering::Greater => r -= 1,
                        Ordering::Equal => {
                            res.push(vec![nums[i], nums[l], nums[r]]);
                            l += 1;
                            r -= 1;
                            while l < n && nums[l] == nums[l - 1] {
                                l += 1;
                            }
                            while r > 0 && nums[r] == nums[r + 1] {
                                r -= 1;
                            }
                        }
                    }
                }
                i += 1;
                while i < n - 2 && nums[i] == nums[i - 1] {
                    i += 1;
                }
            }
            res
        }
    }
    
    

All Problems

All Solutions