赎金信
link：383. 赎金信 - 力扣（LeetCode）
思路分析
关键分析觉得是次数统计，ransomNote中的字符出现次数和magazine中统计次数相同即可.（有点相同字母异序词的味->哈希数组实现【大小写转换】）
题目又说是两个字符串全为小写字母，有数量限制（少量）.方便进行映射.
可以暴力两层for循环求解，但又想到先前接触的哈希map进行映射.
Tip
本题目使用map消耗的空间资源比数组大一些.map要维护红黑树或哈希表还要做哈希函数，更费时.【数据量大时更能体现】
数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] arr = new int[26];
int tmp = 0;
for(int i = 0; i < magazine.length(); i++) {
tmp = magazine.charAt(i) - 'a';
arr[tmp]++;
}
for(int i = 0 ;i < ransomNote.length(); i++) {
tmp = ransomNote.charAt(i) - 'a';
if(arr[tmp] > 0) {
arr[tmp]--;
}else {
return false;
}
}
return true;
}
}
|
三数之和
link：15. 三数之和 - 力扣（LeetCode）
思路分析
最先想的是两两分组，用数组做，然后又想到用哈希map映射，但是题目限制了去重，不是很好操作.
根据提供的示例发现只是三元组不能重复但是组内元素可以相同如[0,0,0].这种情况在去重的时候要考虑进去.避免对{-2，-2，4}这样的数据筛查遗漏.
所以判断条件是
1
| if(i > 0 && nums[i] == nums[i - 1])
|
而不是
1
| if(nums[i] == nums[i + 1])
|
用双指针进行判断【必须是数组排好序】，i在数组起始位置，left在i+1位置，right在数组末尾.i和right先不动，left依次向后遍历，如果三者相加大于0，right向前移动.三折相加小于0，left往后移动.
Tip
三数去重碰到相邻相同元素进行跳过，因为已经判断过一次没必要再判断一次，还要进行减枝避免超时.
双指针
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
37
38
39
40
41
42
| class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
for(int i = 0; i < nums.length; i++) {
if(nums[i] > 0) {
return res;
}
if(i > 0 && nums[i] == nums[i -1]) {
continue;
}
int left = i + 1;
int right = nums.length - 1;
while(right > left) {
int sum = nums[i] + nums[left] + nums[right];
if(sum < 0){
left++;
}else if(sum > 0) {
right--;
}else {
res.add(Arrays.asList(nums[i],nums[left],nums[right]));
while(right > left && nums[right] == nums[right - 1]){
right--;
}
while(right > left && nums[left] == nums[left + 1]) {
left++;
}
right--;
left++;
}
}
}
return res;
}
}
|
