“This is the 27th day of my participation in the Gwen Challenge in November. See details of the event: The Last Gwen Challenge in 2021”
Topic describes
Given an array nums containing n integers, determine if there are three elements a, B, and c in nums such that a + b + c = 0. Please find all the triples that sum to 0 and are not repeated.
Note: Repeated triples cannot be included in the answer.
- Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[1, 1, 2], [1, 1]]
- Example 2:
Input: nums = []
Output: []
- Example 3
Input: nums = [0]
Output: []
- Tip:
0 <= nums.length <= 3000-105 <= nums[i] <= 105
Subject analysis
We first sort the array, using three points I, j, and K to represent the three numbers we are looking for. Determine the first number by enumerating I, i.e., keep one point stationary, consider the change of the other two points, j and k, moving from I + 1 on the left and n-1 on the right, respectively, and find all combinations such as nums[I] + nums[j] + nums[k] == 0. Sum = nums[I] + nums[j] + nums[k] :
- If sum is greater than 0, the right pointer decreases and k moves to the left, making sum smaller
- If and is less than 0, the left pointer adds itself and j moves right, making sum larger
- If sum equals 0, add three elements to the list
The answer must not contain duplicate triples, so when determining the first and second numbers, skip the subscripts with the same number.
Time complexity: O(N^2), where N is the length of array nums.
Space complexity: O(logN). We ignore the space to store the answers, and the space complexity of the extra sort is O(logN). However, we have modified the input array nums, which is not necessarily allowed in practice, so it can also be regarded as using an additional array to store and sort copies of NUMs, with space complexity O(N)O(N).
class Solution { public List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums); int n = nums.length; List<List<Integer>> ans = new ArrayList<List<Integer>>(); if(n<3){ return ans; } for(int i = 0; i<n-2; i++){ if(i>0 && nums[i] == nums[i-1]) continue; int j = i+1,k = n-1; while(j<k){ while(j>i+1 && j<n && nums[j] == nums[j-1]) j++; if(j>=k){ break; } if(nums[i]+nums[j]+nums[k] < 0){ j++; }else if(nums[i]+nums[j]+nums[k] > 0){ k--; }else{ ArrayList<Integer> list = new ArrayList<Integer>(); list.add(nums[i]); list.add(nums[j]); list.add(nums[k]); ans.add(list); j++; } } } return ans; }}Copy the code