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]
代碼實現(xiàn)：
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)
代碼實現(xiàn)：
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
代碼實現(xiàn)：
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]
代碼實現(xiàn)：
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
代碼實現(xiàn)：
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
代碼實現(xiàn)：
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
代碼實現(xiàn):
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)
代碼實現(xiàn)：
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)
代碼實現(xiàn)：
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<>();
// 存在相同的數(shù)卿操，則不再加入target
if (numbers == null || numbers.length < 3) {
return results;
}
Arrays.sort(numbers);
/*遍歷數(shù)組序目，取一個數(shù)的相反數(shù)做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).
代碼實現(xiàn)：
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 個數(shù)的整數(shù)數(shù)組 S，在 S 中找到所有使得和為給定整數(shù) target 的四元組 (a, b, c, d)黑界。
注意事項
- 四元組 (a, b, c, d) 中，需要滿足 a <= b <= c <= d
- 答案中不可以包含重復的四元組。
樣例：
例如，對于給定的整數(shù)數(shù)組 S=[1, 0, -1, 0, -2, 2] 和 target=0. 滿足要求的四元組集合為：
(-1, 0, 0, 1)
(-2, -1, 1, 2)
(-2, 0, 0, 2)
代碼實現(xiàn)：
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);
//選擇第一個數(shù)
for (int i = 0; i < numbers.length - 3; i++) {
//避免選擇重復的數(shù)
if (i != 0 && numbers[i] == numbers[i-1]) {
continue;
}
//選擇第二個數(shù)
for (int j = i+1; j < numbers.length - 2; j++) {
//避免選擇重復的數(shù)
//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加入重復的數(shù)
while (numbers[left] == numbers[left-1]) {
left++;
}
while (numbers[right] == numbers[right+1]) {
right--;
}
}
}
}
}
return result;
}
}
