16 - 最接近的三数之和
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
例1：
1
2
3
| 输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
|
例2：
1
2
| 输入：nums = [0,0,0], target = 1
输出：0
|
思路
采用双指针
my solution
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
33
34
35
36
| class Solution {
public int threeSumClosest(int[] nums, int target) {
int result = nums[0] + nums[1] + nums[2];
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int j = i + 1;
int k = nums.length - 1;
while (j < k) {
int sum = nums[i] + nums[j] + nums[k];
if (sum == target) {
return target;
}
if (Math.abs(sum - target) < Math.abs(result - target)) {
result = sum;
}
if (sum > target) {
int temp = k - 1;
while (j < temp && nums[temp] == nums[k]) {
temp--;
}
k = temp;
}else{
int temp = j+1;
while(temp<k && nums[temp] == nums[j]){
temp++;
}
j = temp;
}
}
}
return result;
}
}
|
17 - 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
例1：
1
2
| 输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
|
例2：
例3：
1
2
| 输入：digits = "2"
输出：["a","b","c"]
|
提示：
0 <= digits.length <= 4digits[i] 是范围 ['2', '9'] 的一个数字。
思路
递归处理
my solution
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
33
34
| class Solution {
private ArrayList<String> result;
private String map[] = {
" ",
"",
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz"
};
public List<String> letterCombinations(String digits) {
result = new ArrayList<>();
if(digits.equals("")){
return result;
}
dfs(digits,0,"");
return result;
}
private void dfs(String digits, int pos, String sb) {
if(pos == digits.length()){
result.add(sb.toString());
return;
}
int temp = digits.charAt(pos) - '0';
for(int i = 0;i<map[temp].length();i++){
dfs(digits,pos+1,sb+map[temp].charAt(i));
}
}
}
|
