双指针解决n数之和问题
1. 两数之和
1. 两数之和
- 将时间复杂度降到O(n)；
class Solution {// 双指针public int[] twoSum(int[] nums, int target) {int n=nums.length;int l=0;while(l<n){int r=n-1;// 找到第一个可能nums[l]+nums[r]==target的位置while(r>l){if(nums[l]+nums[r]==target){return new int[]{l,r};}r--;}l++;}return new int[0];}
}
class Solution {// 哈希表 public int[] twoSum(int[] nums, int target) {int n=nums.length;HashMap<Integer,Integer> map=new HashMap<>();for(int i=0;i<n;i++){map.put(nums[i],i);}for(int i=0;i<n;i++){int another=target-nums[i];if(map.containsKey(another)&&map.get(another)!=i){return new int[]{i,map.get(another)};}}return new int[0];}
}
2. 两数之和 II - 输入有序数组
167. 两数之和 II - 输入有序数组
- 将时间复杂度降到O(n)；
class Solution {// 双指针public int[] twoSum(int[] numbers, int target) {int n=numbers.length;int l=0;while(l<n){int r=n-1;// 找到第一个可能nums[l]+nums[r]==target的位置while(r>l){if(numbers[l]+numbers[r]==target){return new int[]{l+1,r+1};}r--;}l++;}return new int[0];}
}
class Solution {// 双指针public int[] twoSum(int[] numbers, int target) {int l=0,r=numbers.length-1;while(l<r){if(numbers[l]+numbers[r]>target){r--;}else if(numbers[l]+numbers[r]<target){l++;}else{return new int[]{l+1,r+1};}}return new int[0];}
}
3. 三数之和
15. 三数之和
剑指 Offer II 007. 数组中和为 0 的三个数
- 将时间复杂度降到O(n2)；
class Solution {// 排序+双指针// a+b+c=0 ---> a=-(b+c)public List<List<Integer>> threeSum(int[] nums) {// 排序保证重复元素连续Arrays.sort(nums);List<List<Integer>> ans=new ArrayList<>();int n=nums.length;int a=0; // 确定第一个数while(a<n){// 分别确定第二、三个数int c=n-1;int b=a+1;while(b<n){while(c>b&&(-nums[a]<nums[b]+nums[c])){c--;}if(c==b){break;}if(-nums[a]==nums[b]+nums[c]){ // a+b+c=0 可行解List<Integer> cur=new ArrayList<>();cur.add(nums[a]);cur.add(nums[b]);cur.add(nums[c]);ans.add(cur);}// 找到下一个与b不重复的元素int d=b+1;while(d<n&&nums[d]==nums[b]){d++;}b=d;}// 找到下一个与a不重复的元素int e=a+1;while(e<n&&nums[e]==nums[a]){e++;}a=e;}return ans;}
}
class Solution {// 排序+双指针// a+b+c=0 ---> a=-(b+c)public List<List<Integer>> threeSum(int[] nums) {// 排序保证重复元素连续Arrays.sort(nums);List<List<Integer>> ans=new ArrayList<>();int n=nums.length;int a=0; // 确定第一个数while(a<n){// 找到下一个与a不重复的元素if(a==0||nums[a]!=nums[a-1]){// 确定第二个数int b=a+1;int c=n-1;while(b<n){// 找到下一个与b不重复的元素if(b==a+1||nums[b]!=nums[b-1]){// 确定第三个数while(c>b&&(nums[a]+nums[b]>-nums[c])){c--;}if(c==b){break;}if(nums[a]+nums[b]==-nums[c]){ // a+b+c=0 可行解List<Integer> cur=new ArrayList<>();cur.add(nums[a]);cur.add(nums[b]);cur.add(nums[c]);ans.add(cur);}}b++;}}a++;}return ans;}
}
4. 四数之和
18. 四数之和
- 将时间复杂度降到O(n3)；
class Solution {// 排序+双指针public List<List<Integer>> fourSum(int[] nums, int target) {Arrays.sort(nums);List<List<Integer>> ans=new ArrayList<>();int n=nums.length;// 第一个数int a=0;while(a<n){if(a==0||(nums[a]!=nums[a-1])){// 第二个数int b=a+1;while(b<n){if(b==a+1||(nums[b]!=nums[b-1])){// 第三个数int c=b+1;// 第四个数int d=n-1;while(c<n){if(c==b+1||(nums[c]!=nums[c-1])){long sum=nums[a]+nums[b]+nums[c]-target;// 第四个数while(d>c&&((long)nums[a]+nums[b]+nums[c]+nums[d]>target)){d--;}if(d==c){break;}// 可行解if((long)nums[a]+nums[b]+nums[c]+nums[d]==target){List<Integer> cur=new ArrayList<>();cur.add(nums[a]);cur.add(nums[b]);cur.add(nums[c]);cur.add(nums[d]);ans.add(cur);}}c++;}}b++;}}a++;}return ans;}
}