四数之和
点击查看代码
class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {int n = nums.length;Arrays.sort(nums);List<List<Integer>> res = new ArrayList<>();for(int i = 0; i < n - 3 ; i++){if( (long)nums[i]+nums[i+1]+nums[i+2]+nums[i+3] > target){break;}if((long)nums[i]+nums[n-3]+nums[n-2]+nums[n-1] < target){continue;}int x = nums[i];if(i != 0 && nums[i] == nums[i-1]){continue;}int secondTarget = target - x ;for(int j = i+1; j < n-2;j++){if((long)nums[i]+nums[j]+nums[j+1]+nums[j+2] > target){break;}if(nums[i]+nums[j]+nums[n-2]+nums[n-1] < target){continue;}int y = nums[j];if(j != i+1 && nums[j] == nums[j-1]){continue;}int l = j + 1;int r = n - 1;while(l < r){long sum = (long)y + nums[l] + nums[r];if(sum == secondTarget){res.add(Arrays.asList(nums[l],nums[r],y,x));l++;while(l < r && nums[l]==nums[l-1]){l++;}r--;while(l < r && nums[r] == nums[r+1]){r--;} }else if(sum < secondTarget){l++;}else{r--;}}}}return res;}
}
统计和小于目标的下标对数目
点击查看代码
class Solution {public int countPairs(List<Integer> nums, int target) {Collections.sort(nums);int res = 0;int l = 0;int r = nums.size() - 1;while (l < r) {int sum = nums.get(l) + nums.get(r);if (sum < target) {res += (r - l);l++;} else {r--;}}return res;}
}