力扣爆刷第104天之CodeTop100五连刷6-10

力扣爆刷第104天之CodeTop100五连刷6-10

一、15. 三数之和

题目链接：https://leetcode.cn/problems/3sum/description/
思路：求三数之和，需要外层一个for，内层一个for，内层的还要双指针。另外就是要注意去重操作。

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> arrayList = new ArrayList<>();Arrays.sort(nums);for(int i = 0; i < nums.length-2; i++) {if(nums[i] > 0) break;if(i > 0 && nums[i] == nums[i-1]) continue;int j = i+1, k = nums.length-1;while(j < k) {int temp = nums[i] + nums[j] + nums[k];if(temp == 0) {List<Integer> list = new ArrayList<>();list.add(nums[i]);list.add(nums[j]);list.add(nums[k]);arrayList.add(list);while(j < k && nums[j] == nums[j+1]) j++;while(j < k && nums[k] == nums[k-1]) k--;j++;k--;}else if(temp < 0) {j++;}else{k--;}}}return arrayList;}
}

二、53. 最大子数组和

题目链接：https://leetcode.cn/problems/maximum-subarray/description/
思路：可以使用动态规划和贪心来做，动态规划就是状态与选择，贪心就是局部最优到全局最优。
动态规划，定义dp[i]表示在区间nums[0, i]中，以nums[i]为结尾的最大子数组的和，那么对于每一个dp[i]来说，它都可以选择把nums[i]是否追加到子数组的结尾，这个就是状态与选择，选择的条件是最大子数组的和，这一句话就把动态规划讲透了。
贪心：贪心更简单，只要子数组的和大于0我就一直加，只要小于0就离开开启一个新的子数组。

class Solution {public int maxSubArray(int[] nums) {int[] dp = new int[nums.length];dp[0] = nums[0];int max = nums[0];for(int i = 1; i < nums.length; i++) {dp[i] = Math.max(dp[i-1]+nums[i], nums[i]);max = Math.max(max, dp[i]);}return max;}
}

三、912. 排序数组

题目链接：https://leetcode.cn/problems/sort-an-array/description/
思路：使用归并排序，时间复杂度为O(nlogn)，空间复杂度为O(n)。

class Solution {int[] temp;public int[] sortArray(int[] nums) {temp = new int[nums.length];mergeSort(nums, 0, nums.length-1);return nums;}void mergeSort(int[] nums, int left, int right) {if(left >= right) return;int mid = left + (right - left) / 2;mergeSort(nums, left, mid);mergeSort(nums, mid+1, right);int i = left, j = mid + 1;int k = left;while(i <= mid && j <= right) {if(nums[i] <= nums[j]) {temp[k++] = nums[i++]; }else{temp[k++] = nums[j++];}}while(i <= mid) {temp[k++] = nums[i++]; }while(j <= right) {temp[k++] = nums[j++];}k = left;while(k <= right) {nums[k] = temp[k];k++;}}
}

四、21. 合并两个有序链表

题目链接：https://leetcode.cn/problems/merge-two-sorted-lists/description/
思路：合并两个有序链表，类似于归并排序，比大小然后拼接，剩下的，直接拼接。

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode root = new ListNode();ListNode p1 = list1, p2 = list2, p = root;while(p1 != null && p2 != null) {if(p1.val <= p2.val) {p.next = p1;p1 = p1.next;}else{p.next = p2;p2 = p2.next;}p = p.next;p.next = null;}if(p1 != null) {p.next = p1;}if(p2 != null) {p.next = p2;}return root.next;}
}

五、1. 两数之和

题目链接：https://leetcode.cn/problems/two-sum/description/
思路：两数之和，利用map，从map里找target - nums[i]，找到了就找到了。

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> map = new HashMap<>();for(int i = 0; i < nums.length; i++) {int t = target - nums[i];if(map.containsKey(t)) {return new int[] {i, map.get(t)};}else{map.put(nums[i], i);}}return new int[] {-1, -1};}
}