2sum：
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution.
解答：
采用hashmap，从头遍历数组，如果hashmap不含有该元素，则将target减去这个元素的值和该元素的下标存入hashmap；如果hashmap含有该元素，则将hashmap中对应的下标和该元素的下标存入数组返回结果。
public class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> helper = new HashMap<Integer, Integer>();
int[] result = {-1, -1};
for (int i = 0; i < nums.length; i++) {
if (helper.get(nums[i]) != null) {
result[0] = helper.get(nums[i]);
result[1] = i;
return result;
} else {
helper.put(target - nums[i], i);
}
}
return result;
}
}
此题若不是返回下标，还可以采用将数组先进行排序，然后利用左右两个指针寻找相应元素。若左右两指针元素和小于target，则左指针右移，若大于则右指针左移，若相等则返回结果。
public int[] twoSum_pointer(int[] numbers, int target) {
if (numbers == null || numbers.length < 2) {
return null;
}
Arrays.sort(numbers);
int left = 0;
int right = numbers.length - 1;
int[] rst = new int[2];
while ( left < right) {
int sum = numbers[left] + numbers[right];
if( sum == target){
rst[0] = left;
rst[1] = right;
break;
} else if ( sum < target) {
left++;
} else {
right--;
}
}
return rst;
}
3sum：
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.
Note:
- 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.
解答：
运用上题2sum的第二种方法，相当于把数组的每个元素当做target，然后往后寻找2sum为target相反数的两个元素。要注意的是避免重复结果。
public class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new LinkedList<List<Integer>>();
if (nums == null || nums.length < 3) {
return result;
}
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
} //避免重复元素
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
if (nums[i] + nums[left] + nums[right] == 0) {
List<Integer> temp = new LinkedList<Integer>();
temp.add(nums[i]);
temp.add(nums[left]);
temp.add(nums[right]);
result.add(temp);
left++;
right--;
while(left < right && nums[left] == nums[left - 1]) {
left++;
}
while(left < right && nums[right] == nums[right + 1]) {
right--;
} //避免重复元素
} else if (nums[i] + nums[left] + nums[right] > 0) {
right--;
} else {
left++;
}
}
}
return result;
}
}
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. You may assume that each input would have exactly one solution.
解答：同样是2sum的扩展，先将数组排序，然后遍历数组，对每个元素向后寻找两个元素并求和，和等于target直接返回target，大于则左指针右移，小于则右指针左移，同时更新result值。注意，result初始值设为Integer.MAX_VALUE的一半，而不是Integer.MAX_VALUE，否则结果可能溢出而产生错误。比如：
正确代码如下：
public class Solution {
public int threeSumClosest(int[] nums, int target) {
if (nums == null || nums.length < 3) {
return -1;
}
Arrays.sort(nums);
int result = Integer.MAX_VALUE / 2;
for (int i = 0; i < nums.length - 2; i++) {
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int temp = nums[i] + nums[left] + nums[right];
if (temp == target) {
return temp;
} else if (temp < target) {
left++;
} else {
right--;
}
if (Math.abs(temp - target) < Math.abs(result - target)) {
result = temp;
}
}
}
return result;
}
}
4sum:
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note:
- Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
- The solution set must not contain duplicate quadruplets.
解答：
先将数组进行排序，然后两个for循环嵌套，固定两个数组元素，再用左右两指针扫另外两个元素，根据sum与target大小关系确定指针的移动。
public class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new LinkedList<List<Integer>>();
if (nums == null || nums.length < 4) {
return result;
}
Arrays.sort(nums);
for (int i = 0; i < nums.length - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
for (int j = i + 1; j < nums.length - 2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
int left = j + 1;
int right = nums.length - 1;
while (left < right) {
int temp = nums[i] + nums[j] + nums[left] + nums[right];
if (temp == target) {
List<Integer> ele = new LinkedList<Integer>();
ele.add(nums[i]);
ele.add(nums[j]);
ele.add(nums[left]);
ele.add(nums[right]);
result.add(ele);
left++;
right--;
while (left < right && nums[left] == nums[left - 1]) {
left++;
}
while (left < right && nums[right] == nums[right + 1]) {
right--;
}
} else if (temp < target) {
left++;
} else {
right--;
}
}
}
}
return result;
}
}
值得注意的是，本题中的数据结构采用的是LinkedList而不是ArrayList，原因是插入操作比较多，用LinkedList效率更高。前者运行时间击败63%，后者54%。