1. 两数之和

哈希表,将新的数和哈希表里面的数求和看是否等于target;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
int len = nums.length;
for(int i = 0; i < len; i++){
if(map.containsKey(target - nums[i])){
return new int[]{map.get(target - nums[i]), i};
}
if(!map.containsKey(nums[i])){
map.put(nums[i], i);
}
}
return new int[]{};
}
}

283. 移动零

双指针,慢指针p指向非零数字,快指针i遍历数组找到非零数字和p交换;

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public void moveZeroes(int[] nums) {
int p = 0, len = nums.length;
for (int i = 0; i < len; i++) {
if (nums[i] != 0) {
int temp = nums[i];
nums[i] = nums[p];
nums[p] = temp;
p++;
}
}
}
}

3. 无重复字符的最长子串

滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public int lengthOfLongestSubstring(String s) {
int len = s.length();
if(len < 2){
return len;
}

HashMap<Character, Integer> map = new HashMap<>();
int left = -1, right = 0, res = 1;
while(right < len){
char c = s.charAt(right);
if(map.containsKey(c) && map.get(c) > left){
left = map.get(c);
}
map.put(c, right);
res = Math.max(res, right - left);
right++;
}
return res;
}
}

49. 字母异位词分组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
int len = strs.length;
HashMap<String, List<String>> map = new HashMap<>();
for (String str : strs) {
char[] chars = str.toCharArray();
Arrays.sort(chars);
String sorted = new String(chars);
List<String> list = map.getOrDefault(sorted, new ArrayList<>());
list.add(str);
map.put(sorted, list);
}
return new ArrayList<>(map.values());
}
}

128. 最长连续序列

先排序的做法

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
class Solution {
public int longestConsecutive(int[] nums) {
if(nums.length <= 0){
return 0;
}
int res1 = 0, res2 = 0;
Arrays.sort(nums);
int temp = nums[0] - 1;
for(int num : nums){
if(num == temp){

}
else if(num == temp + 1){
res1++;
temp = num;
}
else{
res2 = res1 > res2 ? res1 : res2;
res1 = 1;
temp = num;
}
}

return res1 > res2 ? res1 : res2;
}
}

42. 接雨水

据说每个人都会这道题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int trap(int[] height) {
int left = 0, right = height.length - 1, res = 0;
int leftTop = height[left], rightTop = height[right];
while (left < right) {
leftTop = Math.max(leftTop, height[left]);
rightTop = Math.max(rightTop, height[right]);

if (rightTop > leftTop) {
res += leftTop - height[left++];
} else {
res += rightTop - height[right--];
}
}
return res;
}
}

11. 盛最多水的容器

感觉不如接雨水

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int maxArea(int[] height) {
int res = 0, v = 0;
int left = 0, right = height.length - 1;
int rightTop = height[right], leftTop = height[left];
while(left < right){
if(height[left] < height[right]){
v = height[left] * (right - left);
left++;
}
else{
v = height[right] * (right - left);
right--;
}
res = Math.max(res, v);
}
return res;
}
}

15. 三数之和

双指针做法:

首先将数组排序,然后有一层for循环,i从下标0的地方开始,同时定一个下标left 定义在i+1的位置上,定义下标right 在数组结尾的位置上。

依然还是在数组中找到 abc 使得a + b +c =0,我们这里相当于 a = nums[i],b = nums[left],c = nums[right]。

接下来如何移动left 和right呢?

如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了,因为数组是排序后了,所以right下标就应该向左移动,这样才能让三数之和小一些。

如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了,left 就向右移动,才能让三数之和大一些,直到left与right相遇为止。

然后再处理一下第一个元素i的重复。

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
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
int len = nums.length, sum = 0;
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);

for (int i = 0; i < len; i++) {
if (nums[i] > 0) {
return res;
}
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1, right = len - 1;

while (left < right) {
sum = nums[i] + nums[left] + nums[right];
if (sum < 0) {
left++;
} else if (sum > 0) {
right--;
} else {
res.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));
while (left < right && nums[right - 1] == nums[right]) {
right--;
}
while (left < right && nums[left + 1] == nums[left]) {
left++;
}
right--;
left++;
}
}

}

return res;
}
}

560. 和为 K 的子数组

前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int subarraySum(int[] nums, int k) {
int count = 0, sum = 0;
Map<Integer, Integer> prefixSumCount = new HashMap<>();
prefixSumCount.put(0, 1); // 初始前缀和为0出现1次

for (int num : nums) {
sum += num;
// 查找是否有前缀和等于 sum - k
count += prefixSumCount.getOrDefault(sum - k, 0);
// 记录当前前缀和出现次数
prefixSumCount.put(sum, prefixSumCount.getOrDefault(sum, 0) + 1);
}
return count;
}
}

53. 最大子数组和

解释转载评论区:

要想求区间的和,就只有通过前缀和来计算(否则挨个遍历就会导致时间复杂度过大),这题要维护当前前缀和和最小前缀和

  • 如果当前前缀和比最小前缀和小就更新最小前缀和
  • 用当前前缀和与最小前缀和的差值来求当前符合条件的区间,如果比当前ans大的话就对其更新
    最小前缀和在求完之后再进行更新
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int maxSubArray(int[] nums) {
int ans = -10001, min = 0, sum = 0;
for(int num : nums){
sum += num;
ans = Math.max(sum - min, ans);
if(sum < min){
min = sum;
}
}
return ans;
}
}

56. 合并区间

排序后分类讨论

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
class Solution {
public int[][] merge(int[][] intervals) {
int i, len = intervals.length;
List<int[]> ans = new ArrayList<>();
Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
for (i = 0; i < len - 1; i++) {
if (intervals[i][1] < intervals[i + 1][0]) {
ans.add(intervals[i]);
} else {
int[] temp = intervals[i];
while (i < len - 1 && temp[1] >= intervals[i + 1][0]) {
if (temp[1] < intervals[i + 1][1]) {
temp[1] = intervals[i + 1][1];
}
i++;
}
ans.add(temp);
}
}
if (i != len) {
ans.add(intervals[i]);
}
return ans.toArray(new int[ans.size()][]);
}
}