- Given an array nums of n integers, are there elements a, b, cin 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.
- Example:
- Given array nums = [-1, 0, 1, 2, -1, -4],
- A solution set is:
- [
- [-1, 0, 1],
- [-1, -1, 2]
- ]
- class Solution {
- public List<List<Integer>> threeSum(int[] nums) {
- List<List<Integer>> ret = new ArrayList<>() ;
- if(nums.length==0) return ret;
- int target;
- int len = nums.length-2;
- int left; //point to the left side of the array
- int right; //point to the right side of the array
- Arrays.sort(nums);
- for(int i = 0; i <len; i++){
- target = 0 - nums[i];
- left = i+1;
- right = len+1;
- if(nums[left]> target) break;
- while(left <right){
- if(nums[left] + nums[right]> target){
- right--;
- }
- else if(nums[left] + nums[right] <target){
- left++;
- }
- else{
- List<Integer> ans = new ArrayList<>();
- ans.add(nums[i]);
- ans.add(nums[left]);
- ans.add(nums[right]);
- ret.add(ans);
- //to avoid IndexOutOfBoundsException
- left++;
- right--;
- //for uniqueness
- while(nums[left] == nums[left-1] && left <right) left++;
- while(nums[right] == nums[right+1] && left < right) right--;
- }
- }
- while(nums[i] == nums[i+1]) {
- if(i+1 < len) i++; //for uniqueness
- else return ret;
- }
- }
- return ret;
- }
- }
数组问题注意: 下标越界
时间复杂度: O(n2), 通过两个指针向中间夹逼的方法使得两个数求和的时间复杂度从 O(n2)->O(n).
来源: http://www.bubuko.com/infodetail-3035703.html