Two Sum
题目描述
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.
Example:
Given nums = `[2, 7, 11, 15]`, target = `9`, Because `nums[0]` + `nums[1]` = `2 + 7 = 9`, return `[0, 1]`.
解法
代码如下:
public static int[] twoSum( int[] nums, int target ) {
Map<Integer, Integer> hash = new HashMap<>();
for( int i = 0; i < nums.length; ++i ) {
if( hash.containsKey(target-nums[i]) ) {
return new int[]{ hash.get(target-nums[i]), i };
} else {
hash.put( nums[i], i );
}
}
return null;
}
思考过程: 使用哈希表加快查询.
时空复杂度: 时间复杂度是O(n), 空间复杂度是O(n)
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.
For example, given array S = {-1 0 1 2 -1 -4}, A solution set is: (-1, 0, 1) (-1, -1, 2)
解法
代码如下:
public List<List<Integer>> threeSum( int[] nums ) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort( nums );
for( int i = 0; i < nums.length-2; ++i ) {
if( i != 0 && nums[i] == nums[i-1] ) continue; //去重
int low = i+1, high = nums.length-1, sum = 0 - nums[i];
while( low < high ) {
if( nums[low] + nums[high] == sum ) {
res.add( Arrays.asList( nums[i], nums[low], nums[high] ) );
while( low < high && nums[low] == nums[low+1] ) ++low; //去重
while( low < high && nums[high] == nums[high-1] ) --high; //去重
++low; --high;
} else if( nums[low] + nums[high] < sum ) {
++low;
} else {
--high;
}
}
}
return res;
}
思考过程: 算法思想是建立在有序数组找Two Sum的双指针思想.
首先对数组排序; 从左到右扫描元素[i], 在[i+1...len]这段剩下的范围使用双指针查找.
注意要把重复的情况去掉
时空复杂度: 时间复杂度是O(n^2), 空间复杂度是O(1)
4 Sum
题目描述
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 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)
解法
代码如下:
public List<List<Integer>> fourSum( int[] nums, int target ) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort( nums );
for( int i = 0; i < nums.length-3; ++i ) {
if( i != 0 && nums[i] == nums[i-1] ) continue; //去重
int sum1 = target - nums[i];
for( int j = i+1; j < nums.length-2; ++j ) {
if( j != i+1 && nums[j] == nums[j-1] ) continue; //去重
int sum2 = sum1 - nums[j];
int low = j+1, high = nums.length-1;
while( low < high ) {
if( nums[low] + nums[high] == sum2 ) {
res.add( Arrays.asList( nums[i], nums[j], nums[low], nums[high] ) );
while( low < high && nums[low] == nums[low+1] ) ++low;
while( low < high && nums[high] == nums[high-1] ) --high;
++low; --high;
} else if( nums[low] + nums[high] < sum2 ) {
++low;
} else {
--high;
}
}
}
}
return res;
}
思考过程: 与3 Sum的算法是一模一样的, 所以对于n Sum的问题都可以基于这种算法思想去解决: 把问题不断压缩到2 Sum的情况
时空复杂度: 时间复杂度是O(n^3), 空间复杂度是O(1)