1.两数之和 力扣第一题,题目描述不再贴上来了。关键是数组无序,方法返回值要求是两数的索引 。
常规解法: 双重循环 1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public int [] twoSum(int [] nums, int target) { int n = nums.length; for (int i = 0 ; i < n; i++){ for (int j = i + 1 ; j < n;j++){ if (nums[j] == target - nums[i]){ return new int []{i,j}; } } } return new int [0 ]; } }
HashMap 采用空间换时间的思路,建立值-索引的映射关系。
1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution { public int [] twoSum(int [] nums, int target) { Map<Integer, Integer> hashTable = new HashMap <>(); for (int i = 0 ; i < nums.length; i++){ if (hashTable.containsKey(target - nums[i])){ return new int []{hashTable.get(target - nums[i]),i}; } hashTable.put(nums[i],i); } return new int [0 ]; } }
进阶解法 以下摘自alexhilton的题解
二分法 确定一个数的索引后,在后续的值利用双指针从两头向中间找来节省时间
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 public int [] twoSum(int [] nums, int target) { int [] result = {0 , 1 }; if (nums.length <= 2 ) { return result; } for (int i = 0 ; i < nums.length - 1 ; i++) { result[0 ] = i; int x = target - nums[i]; for (int j = i + 1 , k = nums.length - 1 ; j <= k; j++, k--) { if (nums[j] == x) { result[1 ] = j; return result; } if (nums[k] == x) { result[1 ] = k; return result; } } } return result; }
四分法 相比于二分法,将固定数,也改为二分法。
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 public int [] twoSum(int [] nums, int target) { int [] result = {0 , 1 }; if (nums.length <= 2 ) { return result; } for (int i = 0 , j = nums.length - 1 ; i < j; i++, j--) { if (nums[i] + nums[j] == target) { result[0 ] = i; result[1 ] = j; return result; } int x = target - nums[i]; int y = target - nums[j]; for (int k = i + 1 , m = j - 1 ; k <= m; k++, m--) { result[0 ] = i; if (nums[k] == x) { result[1 ] = k; return result; } else if (nums[m] == x) { result[1 ] = m; return result; } result[1 ] = j; if (nums[k] == y) { result[0 ] = k; return result; } else if (nums[m] == y) { result[0 ] = m; return result; } } } return result; }
时空复杂度分析
双重循环
HashMap
二分法
四分法
时间复杂度
O(n²)
O(n)
O(nlogn)
O(2/nlogn)
空间复杂度
O(1)
O(n)
O(1)
O(1)
两数相加 链表逆序存储两数对应位,考察链表遍历 + 加法进位 的处理。 技巧:dummy虚拟头结点 的使用
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 ListNode addTwoNumbers (ListNode l1, ListNode l2) { ListNode dummy = new ListNode (-1 ); ListNode p = dummy; ListNode p1 = l1, p2 = l2; int carry = 0 ; while (p1 != null || p2 != null || carry != 0 ){ int val = carry; if (p1 != null ){ val += p1.val; p1 = p1.next; } if (p2 != null ){ val += p2.val; p2 = p2.next; } carry = val/10 ; val = val % 10 ; ListNode t = new ListNode (val); p.next = t; p = p.next; } return dummy.next; } }
最长无重复子串 双指针 + 滑动窗口
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public int lengthOfLongestSubstring (String s) { int n = s.length(), res = 0 ; Map<Character, Integer> map = new HashMap <>(); int left = 0 , right = 0 ; while (right < n){ char cr = s.charAt(right); if (map.containsKey(cr)){ left = Math.max(map.get(cr) + 1 , left); } res = Math.max(res, right - left + 1 ); map.put(cr,right); right++; } return res; } }
正序数组中位数 要求时间复杂度为O(log(m+n)) 联想到二分法 解题。
二分法(官方) 力扣官方
进阶解法: 假设中位数索引值为k 利用中位数特点与第k小结合; 在长度更短的数组里寻找最大的索引m(其下标不超过K),其小于更长数组k - m -1下标处的值。 m-1、k-m-1分别锁定了两个数组处于前K个最小数里的最大值的下标。 由中位数特点可知: 当两数组长度之和为奇数时,应在边界附近(此解法在边界左侧) 当两数组长度之和为偶数时,应取边界左侧(前K个数最大值)和右侧(两数组在前K个数里最大值下标+1后的最小值)的平均值。 时间复杂度:O(log min(m,n))
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 double findMedianSortedArrays (int [] nums1, int [] nums2) { int n = nums1.length; int m = nums2.length; if (n>m){ return findMedianSortedArrays(nums2, nums1); } int k = (n + m + 1 )/2 ; int left = 0 ; int right=n; while (left < right){ int m1 = left + (right - left) /2 ; int m2 = k - m1; if (nums1[m1] < nums2[m2 - 1 ]){ left = m1 + 1 ; } else { right = m1; } } int m1 = left; int m2 = k - left; int c1 = Math.max(m1 <= 0 ? Integer.MIN_VALUE : nums1[m1-1 ], m2 <= 0 ? Integer.MIN_VALUE : nums2[m2-1 ]); if ((n + m)%2 ==1 ) return c1; int c2 = Math.min(m1 >= n ? Integer.MAX_VALUE : nums1[m1], m2 >= m ? Integer.MAX_VALUE : nums2[m2]); return (c1 + c2) * 0.5 ; } }