哈希表，将新的数和哈希表里面的数求和看是否等于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[]{};
}
}
|
双指针，慢指针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++;
}
}
}
}
|
滑动窗口
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;
}
}
|
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());
}
}
|
先排序的做法
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;
}
}
|
据说每个人都会这道题
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;
}
}
|
感觉不如接雨水
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;
}
}
|
前缀和
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);
for (int num : nums) {
sum += num;
count += prefixSumCount.getOrDefault(sum - k, 0);
prefixSumCount.put(sum, prefixSumCount.getOrDefault(sum, 0) + 1);
}
return count;
}
}
|
解释转载评论区：
要想求区间的和，就只有通过前缀和来计算（否则挨个遍历就会导致时间复杂度过大），这题要维护当前前缀和和最小前缀和
- 如果当前前缀和比最小前缀和小就更新最小前缀和
- 用当前前缀和与最小前缀和的差值来求当前符合条件的区间，如果比当前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;
}
}
|
排序后分类讨论
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()][]);
}
}
|
