119. Pascal’s Triangle II
Given an index k, return the kth row of the Pascal’s triangle.
For example, given k = 3,
Return [1,3,3,1].
**题目：返回帕斯卡三角的第k行。
思路：倒着计算第k行的元素，就可以只在O(k)的空间内计算。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.ArrayList;
class Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> res = new ArrayList<Integer>(rowIndex + 1);
for(int i = 0; i < rowIndex + 1; i++){
res.add(1);
}
for(int i = 2; i < rowIndex + 1;i++){
for(int j = i - 1; j >= 1; j--){
res.set(j, res.get(j) + res.get(j-1));
}
}
return res;
}
}
1. 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, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
题目：给定target，在数组中找出相加等于target的一组数字，假定有且只有一组解。
思路：利用HashMap，一边将数组中的数字nums[i]放进HashMap，一边查找是否有key为target - nums[i]，如果有，则返回其键值。
1
2
3
4
5
6
7
8
9
10
import java.util.HashMap;
class Solution {
public int[] twoSum(int[] numbers, int target) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < numbers.length; map.put(numbers[i], i++))
if (map.containsKey(target - numbers[i]))
return new int[]{map.get(target - numbers[i]),i};
return new int[]{0,0};
}
}
15. 3Sum
Given an array nums of n integers, are there elements a, b, c in nums 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.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
题目：在数组中寻找相加为0的三个数字，要求得到解不重复。
思路：将数组排序之后，遍历数组，将第i个数字nums[i]的相反数作为 two sum的target，设置一个left游标从i+1开始遍历，right游标从nums.lengh - 1 开始遍历，若nums[left] + nums[right] < target 那么需要将left+1，反之right - 1。为了避免重复，在i遍历的时候，若自身等于前一个遍历过的数，就直接跳过；在left和right遍历的时候，若下一个也等于自身，那么也可以跳过。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.ArrayList;
import java.util.Arrays;
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
Arrays.sort(nums);
for(int i = 0; i < nums.length - 1; i++){
if(nums[i] > 0) break;
if(i > 0 && nums[i] == nums[i - 1]) continue;
int target = 0 - nums[i];
int left = i + 1, right = nums.length - 1;
while(left < right){
if(nums[left] + nums[right] == target) {
ArrayList<Integer> grp = new ArrayList<Integer>();
grp.add(nums[i]);
grp.add(nums[left]);
grp.add(nums[right]);
res.add(grp);
while(left < right && nums[left] == nums[left + 1]) left++;
while(left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
}
else if(nums[left] + nums[right] < target) left++;
else if(nums[left] + nums[right] > target) right--;
}
}
return res;
}
}
16. 3Sum Closest
Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
Example:
Given array nums = [-1, 2, 1, -4], and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
题目：给定一个target和数组，求与target最接近的3个数之和，并返回这个和。
思路：与之前3sum类似，只是换了一个目标，因此我们只需要多记录一个min和一个res，存储3sum与target的差值，没次min被更新的时候将3sum存储到res中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.Arrays;
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int min = Integer.MAX_VALUE, res = 0;
for(int i = 0; i < nums.length; i++){
if(i > 0 && nums[i] == nums[i - 1]) continue;
int j = i + 1, k = nums.length - 1;
while(j < k){
int diff = Math.abs(nums[i] + nums[j] + nums[k] - target);
int sum = nums[i] + nums[j] + nums[k];
if(min > diff){
min = diff;
res = sum;
}
if(sum < target) j++;
if(sum > target) k--;
if(sum == target) return sum;
}
}
return res;
}
}
18. 4Sum
Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums 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.
Example:
Given array nums = [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]
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.ArrayList;
import java.util.Arrays;
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(nums.length < 4) return res;
Arrays.sort(nums);
for(int i = 0; i < nums.length; i++){
if(i > 0 && nums[i] == nums[i - 1]) continue;
for(int j = i + 1; j < nums.length; j++){
if(j > i + 1 && nums[j] == nums[j -1]) continue;
int k = j + 1, l = nums.length - 1;
while(k < l){
int sum = nums[i] + nums[j] + nums[k] + nums[l];
if(sum == target){
res.add(Arrays.asList(nums[i], nums[j], nums[k], nums[l]));
while(k < l && nums[k] == nums[k + 1]) k++;
while(k < l && nums[l] == nums[l - 1]) l--;
k++;
l--;
}
else if(sum > target) l--;
else if(sum < target) k++;
}
}
}
return res;
}
}