文章目录
1. 两数之和
https://leetcode-cn.com/problems/two-sum/
- 按任意顺序返回答案
- 返回的是数组下标
使用一个HashMap 存储下之前记录的数值即可。
public class Solution {
public int[] twoSum(int[] nums, int target) {
if (nums == null) {
return null;
}
//<num数值，index> 结果需要返回 index
HashMap<Integer, Integer> numMap = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++) {
if (numMap.containsKey(target - nums[i])) {
return new int[]{
numMap.get(target - nums[i]), i};
}
numMap.put(nums[i], i);
}
return new int[0];
}
}
- 时间复杂度：O(n)
- 空间复杂度；O(n)
2. 三数之和
https://leetcode-cn.com/problems/3sum/
方法一：使用哈希表存储第三个数字，然后使用两数之和的思路
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
if (nums == null) {
return null;
}
HashMap<Integer, Integer> numMap = new HashMap<Integer, Integer>();
Set<List<Integer>> result = new HashSet<List<Integer>>();
for (int i = 0; i < nums.length; i++) {
//从这里开始两数之和的思路
numMap.clear();
for (int j = i + 1; j < nums.length; j++) {
int threeVal = -(nums[i] + nums[j]);
if (numMap.containsKey(threeVal)) {
List<Integer> list = new ArrayList<Integer>();
list.add(nums[i]);
list.add(nums[j]);
list.add(threeVal);
//返回的list是有序的
list.sort(Comparator.naturalOrder());
result.add(list);
}
numMap.put(nums[j], j);
}
}
//答案中不可以包含重复的三元组。
return new ArrayList<List<Integer>>(result);
}
}
- 时间复杂度：O(n^2)
- 空间复杂度；O(n)
方法二：夹逼法
- sort&&find
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
if (nums == null) {
return null;
}
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
// 剪枝:如果已经大于0，那绝对就是找不到其余两个数字了
if (nums[i] > 0) return result;
//对 num[i] 直接进行去重
if (i > 0 && nums[i - 1] == nums[i]) continue;
//左右进行夹逼，left 往右移动，之和变大，right 往左移动，之和变小
int left = i + 1;
int right = nums.length - 1;
//记住三个循环的一个结构
while (left < right) {
if (nums[left] + nums[right] + nums[i] < 0) {
left++;
} else if (nums[left] + nums[right] + nums[i] > 0) {
right--;
} else {
// 三数之和为 0 了
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
//对 left 和 right 进行去重
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
// 修改指针：因为可能存在这种不止一种情况。如： -10 -9 -8 18 19
left++;
right--;
}
}
}
return result;
}
}
- 时间复杂度：O(n^2)
- 空间复杂度；O(1)
3. 四数之和
4. 有效的字母异位词
https://leetcode-cn.com/problems/valid-anagram/
class Solution {
public boolean isAnagram(String s, String t) {
if (s == null || t == null || s.length() != t.length()) {
return false;
}
Map<String, Integer> countMap = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
String key = String.valueOf(s.charAt(i));
if (!countMap.containsKey(String.valueOf(s.charAt(i)))) {
countMap.put(key, 1);
} else {
countMap.put(key, countMap.get(String.valueOf(s.charAt(i))) + 1);
}
}
for (int i = 0; i < t.length(); i++) {
String key = String.valueOf(t.charAt(i));
if (!countMap.containsKey(key)) {
return false;
}
countMap.put(key, countMap.get(key) - 1);
if (countMap.get(key) == 0) {
countMap.remove(key);
}
}
return countMap.isEmpty();
}
}
剑指 Offer 50. 第一个只出现一次的字符
https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/
class Solution {
public char firstUniqChar(String s) {
// 字符 ：数组下标
HashMap<Character, Integer> positionMap = new HashMap<>();
int len = s.length();
for (int i = 0; i < len; i++) {
if (positionMap.containsKey(s.charAt(i))) {
positionMap.put(s.charAt(i), -1);
} else {
positionMap.put(s.charAt(i), i);
}
}
int first = len;
// 遍历：这里注意需要找到最小的 pos
for (Map.Entry<Character, Integer> entry : positionMap.entrySet()) {
int pos = entry.getValue();
if (pos != -1 && pos < first) {
first = pos;
}
}
return first == len ? ' ' : s.charAt(first);
}
}
- 时间：O(n)
- 空间：O(n)