K-sum
1. 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, and you may not use the same element twice.
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
- 没有排序，我们需要计算任意两个元素的和判断是否等于target。将所有的相加的元素和铺展开来是一个n-by-n的矩阵。这是一个Naive O(n^2)方法。
- 我们可以用<u>HashMap法</u>去记住访问的值。key存值，value存索引值。RT=O(n)。runtime beats 100%。但是会利用额外的空间O(n)，这是一个典型的space-time tradeoff。
public class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> m = new HashMap<Integer,Integer>();
int[] res = new int[2];
for(int i = 0; i < nums.length; i++){
if(m.containsKey(target - nums[i])){
res[0] = m.get(target - nums[i]);
res[1] = i;
break;
}
m.put(nums[i], i);
}
return res;
}
}
2. 2sum II:
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.
You may assume that each input would have exactly one solution and you may not use the same element twice.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
- 用HashMap来做这道题，能够AC，但是runtime beats 9.6%，不够有效。
- 首先由于是一个排序好的的序列，我们可以联想到<u>二分法</u>。二分法是搜索是对一个元素进行查找。
- 对两个元素查找可以用<u>two pointers</u>方法。其次由于是一个排序好的，对于上面的矩阵，行和列都是递增的。我们可以用一大一小的指针。RT=O(n),SP=O(1)。 RT beats 44.3%(当在目标元素中间时，有时候提交会LTE)
- 对于第一题unsorted，另一种解法先排序再用双指针法。RT=O(nlogn)。
public class Solution {
public int[] twoSum(int[] num, int target) {
int[] indice = new int[2];
//边界判断是很重要的。
if (num == null || num.length < 2) return indice;
int left = 0, right = num.length - 1;
while (left < right ) {
//这里其实需要防止int相加溢出，可以用long
if (num[left] + num[right] == target) {
indice[0] = left + 1;
indice[1] = right + 1;
break;
}
else if (num[left] + num[right] > target) right--;
else left ++;
}
return indice;
}
}
3. 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: The solution set must not contain duplicate triplets.
For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
- 这里首先想到的是naive办法，三重循环，其结果是RT=O(n^3),且不能检查重复（其实可以用HashSet）。
- 其次想到用HashMap存储数组，对数组俩俩求和再与HashMap中的value比较，这样仍然会有重复以及与自己相加的问题。
- 由上一题我们联想到：先排序，固定一个数，在剩下的书中用做一个2sum，三者和等于target。同时检查重复。RT beats 58%~70%(还有更好的方法？)
public class Solution {
public List<List<Integer>> threeSum(int[] nums) {
ArrayList<List<Integer>> result = new ArrayList<List<Integer>>();
if(nums == null || nums.length < 3)return result;
Arrays.sort(nums);
for(int i = 0; i < nums.length - 2; i++){
if(nums[i >0])break;
//nums[i] > nums[i-1] to avoid duplicate solutuions
if(i == 0 || nums[i] > nums[i-1]){
int opp = -nums[i];
int l = i +1;
int r = nums.length-1;
while(l < r){
if(nums[l]+nums[r] == opp){
List<Integer> temp = new ArrayList<Integer>();
// already sorted
//res.add(Arrays.asList(num[i], num[l], num[R]));
temp.add(nums[i]);
temp.add(nums[l]);
temp.add(nums[r]);
result.add(temp);
//change both l & r
l++;
r--;
//avoid duplicate solutuions
while(l < r && nums[l] == nums[l-1])l++;
while(l < r && nums[r] == nums[r+1])r--;
}else if(nums[l]+nums[r] > opp)r--;
else l++;
}
}
}
return result;
}
}
学习一下别人的代码风格（但是RT会增加，？）
public class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if(nums.length < 3) return result;
Arrays.sort(nums);
int i = 0;
while(i < nums.length - 2) {
if(nums[i] > 0) break;
int j = i + 1;
int k = nums.length - 1;
while(j < k) {
int sum = nums[i] + nums[j] + nums[k];
if(sum == 0) result.add(Arrays.asList(nums[i], nums[j], nums[k]));
if(sum <= 0) while(nums[j] == nums[++j] && j < k);
if(sum >= 0) while(nums[k--] == nums[k] && j < k);
}
while(nums[i] == nums[++i] && i < nums.length - 2);
}
return result;
}
}
4. 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: The solution set must not contain duplicate quadruplets.
For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.
A solution set is:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
- 到了4sum，已经可以完全找到规律：固定一个值，在剩下的值中做3sum（只需在3sum外套一层循环）。RT=O(n^3)。
- 推广到Ksum，递归的做2~k sum。RT=O(n^k-1)。
public class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
ArrayList<List<Integer>> result = new ArrayList<List<Integer>>();
if(nums == null || nums.length < 4)return result;
Arrays.sort(nums);
for(int p = 0; p < nums.length-3; p++ ){
//if(nums[p]>target)return result;当target<0时不成立。如(-5) > (-9), (-5)+(-4) = (-9)
if(p == 0 || nums[p] > nums[p-1]){
int res = target -nums[p];
for(int i = p+1; i < nums.length - 2; i++){
//if(nums[i] > res)break;
//nums[i] > nums[i-1] to avoid duplicate solutuions
if(i == p+1 || nums[i] > nums[i-1]){
int opp = res -nums[i];
int l = i +1;
int r = nums.length-1;
while(l < r){
if(nums[l]+nums[r] == opp){
List<Integer> temp = new ArrayList<Integer>();
// already sorted
//res.add(Arrays.asList(num[i], num[l], num[R]));
temp.add(nums[p]);
temp.add(nums[i]);
temp.add(nums[l]);
temp.add(nums[r]);
result.add(temp);
//change both l & r
l++;
r--;
//avoid duplicate solutuions
while(l < r && nums[l] == nums[l-1])l++;
while(l < r && nums[r] == nums[r+1])r--;
}else if(nums[l]+nums[r] > opp)r--;
else l++;
}
}
}
}
}
return result;
}
}
另一种Hash方法，RT=O(n^2)。
