Two Sum
题目：
Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are NOT zero-based.
样例：
numbers=[2, 7, 11, 15], target=9
return [1, 2]
代码实现：
public class Solution {
/*
* @param numbers : An array of Integer
* @param target : target = numbers[index1] + numbers[index2]
* @return : [index1 + 1, index2 + 1] (index1 < index2)
*/
public int[] twoSum(int[] numbers, int target) {
if (numbers == null || numbers.length == 0) {
return new int[0];
}
Map<Integer, Integer> map = new HashMap<>();
// List<Integer> list = new ArrayList<>();
// Arrays.sort(numbers);
for (int i = 0; i < numbers.length; i++) {
if (map.containsKey(numbers[i])) {
int[] result = {map.get(numbers[i])+1, i+1};
return result;
// list.add(map.get(numbers[i]));
//list.add(i+1);
} else {
map.put(target-numbers[i], i);
}
}
int[] result = {};
return result;
}
}
Two Sum - Greater than target
题目：
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.
样例：
numbers = [2, 7, 11, 15], target = 24.
Return 1. (11 + 15 is the only pair)
代码实现：
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 left = 0;
right = nums.length - 1;
int count = 0;
while (left < right) {
if (nums[left] + nums[right] <= target) {
left++;
} else {
count += right - left;
right--;
}
}
return count;
}
}
Two Sum - Data structure design
题目：
Design and implement a TwoSum class. It should support the following operations: add and find.
- add - Add the number to an internal data structure.
- find - Find if there exists any pair of numbers which sum is equal to the value.
样例 :
add(1); add(3); add(5);
find(4) // return true
find(7) // return false
代码实现：
public class TwoSum {
private List<Integer> list = null;
private Map<Integer, Integer> map = null;
public TwoSum() {
list = new ArrayList<Integer>();
map = new HashMap<Integer, Integer>();
}
// Add the number to an internal data structure.
public void add(int number) {
if (map.containsKey(number)) {
map.put(number, map.get(number)+1);
} else {
map.put(number, 1);
list.add(number);
}
}
// Find if there exists any pair of numbers which sum is equal to the value.
public boolean find(int value) {
for (int i = 0; i < list.size(); i++) {
int num1 = list.get(i), num2 = value - num1;
if ((num1 == num2 && map.get(num1) > 1)
|| (num1 != num2 && map.containsKey(num2))) {
return true;
}
}
return false;
}
}
// Your TwoSum object will be instantiated and called as such:
// TwoSum twoSum = new TwoSum();
// twoSum.add(number);
// twoSum.find(value);
Two Sum - Input array is sorted
题目：
Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
- The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
样例 ：
Given nums = [2, 7, 11, 15], target = 9
return [1, 2]
代码实现：
public class Solution {
/*
* @param nums an array of Integer
* @param target = nums[index1] + nums[index2]
* @return [index1 + 1, index2 + 1] (index1 < index2)
*
* Two-Pointers
*/
public int[] twoSum(int[] nums, int target) {
int left = 0;
int right = nums.length-1;
while (left < right) {
if (nums[left] + nums[right] == target) {
int[] result = new int[2];
result[0] = left + 1;
result[1] = right +1;
return result;
} else if (nums[left] + nums[right] < target) {
left++;
} else {
right--;
}
}
int[] result = {};
return result;
}
}
Two Sum - Unique pairs
题目：
Given an array of integers, find how many unique pairs in the array such that their sum is equal to a specific target number. Please return the number of pairs.
样例：
Given nums = [1,1,2,45,46,46], target = 47
return 2
1 + 46 = 47
2 + 45 = 47
代码实现：
public class Solution {
/**
* @param nums an array of integer
* @param target an integer
* @return an integer
*/
public int twoSum6(int[] nums, int target) {
if (nums == null || nums.length < 2) {
return 0;
}
int left = 0;
int right = nums.length-1;
int count = 0;
Arrays.sort(nums);
while (left < right) {
if (nums[left]+nums[right] == target) {
count++;
left++;
right--;
while(left < right && nums[left] == nums[left-1]) {
left++;
}
while(left < right && nums[right] == nums[right+1]) {
right--;
}
} else if (nums[left]+nums[right] > target) {
right--;
} else {
left++;
}
}
return count;
}
}
Two Sum - Closest to target
题目：
Given an array nums of n integers, find two integers in nums such that the sum is closest to a given number, target.
Return the difference between the sum of the two integers and the target.
样例 ：
nums = [-1, 2, 1, -4],target = 4.
最接近值为 1
代码实现：
public class Solution {
/**
* @param nums an integer array
* @param target an integer
* @return the difference between the sum and the target
*/
public int twoSumClosest(int[] nums, int target) {
if (nums == null || nums.length < 2) {
return -1;
}
Arrays.sort(nums);
int left = 0;
int right = nums.length-1;
int diff = Integer.MAX_VALUE;
while (left < right) {
if (nums[left] + nums[right] < target) {
diff = Math.min(diff, target-nums[left]-nums[right]);
left++;
} else {
diff = Math.min(diff, nums[left]+nums[right]-target);
right--;
}
}
return diff;
}
}
Two Sum-Less than or Equal to target
题目:
Given an array of integers, find how many pairs in the array such that their sum is less than or equal to a specific target number. Please return the number of pairs.
样例:
Given nums = [2, 7, 11, 15], target = 24.
Return 5.
2 + 7 < 24
2 + 11 < 24
2 + 15 < 24
7 + 11 < 24
7 + 15 < 25
代码实现:
public class Solution {
/**
* @param nums an array of integer
* @param target an integer
* @return an integer
*/
public int twoSum5(int[] nums, int target) {
if (nums == null || nums.length < 2) {
return 0;
}
Arrays.sort(nums);
int left = 0;
int right = nums.length-1;
int count = 0;
while (left < right) {
while (left < right && nums[left] + nums[right] > target) {
right--;
}
while (left < right && nums[left] + nums[right] <= target) {
count += right - start;
left++;
}
}
return count;
}
}
Two Sum - Difference equals to target
题目：
Given an array of integers, find two numbers that their difference equals to a target value.
where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are NOT zero-based.
样例：
nums = [2, 7, 15, 24], target = 5
return [1, 2] (7 - 2 = 5)
代码实现：
class Pair {
int idx;
int num;
public Pair(int i, int num) {
this.idx = i;
this.num =num;
}
}
public class Solution {
/*
* @param nums an array of Integer
* @param target an integer
* @return [index1 + 1, index2 + 1] (index1 < index2)
*/
public int[] twoSum7(int[] nums, int target) {
int[] indexs = new int[2];
if (nums == null || nums.length < 2)
return indexs;
if (target < 0)
target = -target;
int n = nums.length;
Pair[] pairs = new Pair[n];
for (int i = 0; i < n; ++i)
pairs[i] = new Pair(i, nums[i]);
Arrays.sort(pairs, new Comparator<Pair>(){
public int compare(Pair p1, Pair p2){
return p1.num - p2.num;
}
});
int j = 0;
for (int i = 0; i < n; ++i) {
if (i == j)
j ++;
while (j < n && pairs[j].num - pairs[i].num < target)
j ++;
if (j < n && pairs[j].num - pairs[i].num == target) {
indexs[0] = pairs[i].idx + 1;
indexs[1] = pairs[j].idx + 1;
if (indexs[0] > indexs[1]) {
int temp = indexs[0];
indexs[0] = indexs[1];
indexs[1] = temp;
}
return indexs;
}
}
return indexs;
}
}
Three-Sum
题目：
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
- Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
- The solution set must not contain duplicate triplets.
样例：
S = {-1 0 1 2 -1 -4}, A solution set is:
(-1, 0, 1)
(-1, -1, 2)
代码实现：
public class Solution {
/**
* @param numbers : Give an array numbers of n integer
* @return : Find all unique triplets in the array which gives the sum of zero.
*/
public ArrayList<ArrayList<Integer>> threeSum(int[] numbers) {
ArrayList<ArrayList<Integer>> results = new ArrayList<>();
// 存在相同的数，则不再加入target
if (numbers == null || numbers.length < 3) {
return results;
}
Arrays.sort(numbers);
/*遍历数组，取一个数的相反数做target
*i < numbers.length-2 保留最后2个，twoSum
*/
for (int i = 0; i < numbers.length; i++) {
if (i > 0 && numbers[i] == numbers[i-1]) {
continue;
}
int left = i+1;
int right = numbers.length-1;
int target = -numbers[i];
twoSum(numbers, left, right,target, results);
}
return results;
}
private void twoSum(int[] numbers,
int left,
int right,
int target,
ArrayList<ArrayList<Integer>> results) {
while (left < right) {
if (numbers[left]+numbers[right] == target) {
ArrayList<Integer> list = new ArrayList<>();
list.add(-target);
list.add(numbers[left]);
list.add(numbers[right]);
left++;
right--;
results.add(list);
// 去除重复加入的情况
while (left < right && numbers[left] == numbers[left-1]) {
left++;
}
while (left < right && numbers[right] == numbers[right+1]) {
right--;
}
} else if (numbers[left]+numbers[right] > target) {
right--;
} else {
left++;
}
}
}
}
3Sum Closest
题目：
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers.
样例：
array S = [-1 2 1 -4], and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
代码实现：
public class Solution {
/**
* @param numbers: Give an array numbers of n integer
* @param target : An integer
* @return : return the sum of the three integers, the sum closest target.
*/
public int threeSumClosest(int[] numbers, int target) {
if (numbers == null || numbers.length < 3) {
return -1;
}
Arrays.sort(numbers);
int bestSum = numbers[0]+numbers[1]+numbers[2];
for (int i = 0; i < numbers.length; i++) {
int left = i+1;
int right = numbers.length-1;
while(left < right) {
int sum = numbers[i]+numbers[left]+numbers[right];
if (Math.abs(sum-target) < Math.abs(bestSum-target)) {
bestSum = sum;
}
if (sum < target) {
left++;
} else {
right--;
}
}
}
return bestSum;
}
}
Four-Sum
题目：
给一个包含 n 个数的整数数组 S，在 S 中找到所有使得和为给定整数 target 的四元组 (a, b, c, d)。
注意事项
- 四元组 (a, b, c, d) 中，需要满足 a <= b <= c <= d
- 答案中不可以包含重复的四元组。
样例：
例如，对于给定的整数数组 S=[1, 0, -1, 0, -2, 2] 和 target=0. 满足要求的四元组集合为：
(-1, 0, 0, 1)
(-2, -1, 1, 2)
(-2, 0, 0, 2)
代码实现：
public class Solution {
/**
* @param numbers : Give an array numbersbers of n integer
* @param target : you need to find four elements that's sum of target
* @return : Find all unique quadruplets in the array which gives the sum of
* zero.
*/
public ArrayList<ArrayList<Integer>> fourSum(int[] numbers, int target) {
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
Arrays.sort(numbers);
//选择第一个数
for (int i = 0; i < numbers.length - 3; i++) {
//避免选择重复的数
if (i != 0 && numbers[i] == numbers[i-1]) {
continue;
}
//选择第二个数
for (int j = i+1; j < numbers.length - 2; j++) {
//避免选择重复的数
//if (j != 0 && numbers[j] == numbers[j-1]) {
//j的取值应该依i而定
if (j != i+1 && numbers[j] == numbers[j-1]) {
continue;
}
int left = j+1;
int right = numbers.length-1;
while (left < right) {
int sum = numbers[i] + numbers[j] + numbers[left] + numbers[right];
if (sum < target) {
left++;
} else if (sum > target) {
right--;
} else {
ArrayList<Integer> list = new ArrayList<>();
list.add(numbers[i]);
list.add(numbers[j]);
list.add(numbers[left]);
list.add(numbers[right]);
result.add(list);
left++;
right--;
//避免3、4加入重复的数
while (numbers[left] == numbers[left-1]) {
left++;
}
while (numbers[right] == numbers[right+1]) {
right--;
}
}
}
}
}
return result;
}
}
