Two Sum II
23% Accepted
Given an array of integers, find how many pairs in the array such that their sum is bigger than a specific target number. Please return the number of pairs.
Example
numbers=[2, 7, 11, 15], target=24
return 1
Challenge
Either of the following solutions are acceptable: O(1) Space, O(nlogn) Time
Tags Expand
- Two Pointers
思路
- easy
- 类似于two sum, 但是画图
- 因为是大于不再是等于了,所以不能再使用hashmap来优化了
- 这个时候采取two sum的另一种做法, 利用排序来做
- 这个题还有一些小trick
- 找到 nums[start] + nums[end] > target 并不是count++, 很容易在这里犯错
- 比如[3,4,5,7,8] target = 9
- start = 0 ,end = 4, 3 + 8 > 9, end--
- 这个时候不是count++,因为4+8 5+8 7+8 都会大于target
- 所以是count = count + end - start
public class Solution {
/**
* @param nums: an array of integer
* @param target: an integer
* @return: an integer
*/
public int twoSum2(int[] nums, int target) {
// Write your code here
if (nums == null || nums.length < 2) {
return 0;
}
Arrays.sort(nums);
int count = 0;
int start = 0;
int end = nums.length - 1;
while (start < end) {
if (nums[start] + nums[end] > target) {
count = count + end - start;
end--;
} else if (nums[start] + nums[end] <= target) {
start++;
}
}
return count;
}
}