1-20

1.给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解法：暴力法，循环遍历数组两次，下标相等时推出本次循环。这种方法的时间复杂度为O（n²）。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for(int i=0;i<nums.length;i++){
            for(int j=0;j<nums.length;j++){
                if(i==j) continue;
                if(nums[i]+nums[j]==target){
                    int[] ans={i,j};
                    return ans;
                }
            }
        }
        return null;
    }
}

执行用时 : 99 ms
内存消耗 : 36.7 MB

如何能更快一点呢？

需要一种更有效的方法来检查数组中是否存在目标元素。如果存在，我们需要找出它的索引。保持数组中的每个元素与其索引相互对应的最好方法是什么？

哈希表。

一次迭代哈希表。在第一次迭代中，将每个元素的值和它的索引添加到表中，同时检查表中是否存在当前元素对应的目标元素，若存在，就找到解，并返回。

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

执行用时 : 7 ms
内存消耗 : 38.2 MB

2.给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

解法：解题方法类似于在纸上做加法，同位数相加，进位。容易犯错的是，最后一次同位数相加后，可能产生进位，容易被忽略。

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode newList=new ListNode(0);
        ListNode q=l1,p=l2,curr=newList;
        int carry=0;
        while(q!=null||p!=null){
            int x=(q!=null)?q.val:0;
            int y=(p!=null)?p.val:0;
            int sum=x+y+carry;
            carry=sum/10;
            curr.next=new ListNode(sum%10);
            if(q!=null) q=q.next;
            if(p!=null) p=p.next;
            curr=curr.next;
        }
        if(carry>0){
            curr.next=new ListNode(carry);
        }
        return newList.next;
    }
}

3.给定一个字符串，请找出其中不含有重复字符的 最长子串 的长度。
解决方法：

• 暴力法：逐个检查所有子字符串，看是否有重复字符。时间复杂度为O（n³）。
• 滑动窗口：使用HashSet作为滑动窗口，将字符存储在当前窗口[i,j),然后向右滑动索引j，如果它不存在HashSet中，继续滑动j。直到s[j]存在HashSet中。此时找到最长无重复字符子串以索引i开头。时间复杂度为O（n）。

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Set<Character> set = new HashSet<>();
        int ans = 0, i = 0, j = 0;
        while (i < n && j < n) {
            // try to extend the range [i, j]
            if (!set.contains(s.charAt(j))){
                set.add(s.charAt(j++));
                ans = Math.max(ans, j - i);
            }
            else {
                set.remove(s.charAt(i++));
            }
        }
        return ans;
    }
}

优化：实际上，如果s[j]在[i,j）内有与k重复字符，不需要逐渐增加i。可以直接跳过[i,k],将i变为k+1。

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>(); // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)), i);
            }
            ans = Math.max(ans, j - i + 1);
            map.put(s.charAt(j), j + 1);
        }
        return ans;
    }
}

4.给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。请找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。你可以假设 nums1 和 nums2 不会同时为空。
示例：

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

解答：由于有时间复杂度限制，所以不能使用两个指针分别指向两个数组来遍历，因为这样的时间复杂度是O（m+n）。要利用中位数的作用，中位数左右两边的个数相等，官方用到的递归法结合了分治法和二分查找。我实现的方法不能满足时间复杂度要求。

class Solution {
    public double findMedianSortedArrays(int[] A, int[] B) {
        int m = A.length;
        int n = B.length;
        if (m > n) { // to ensure m<=n
            int[] temp = A; A = B; B = temp;
            int tmp = m; m = n; n = tmp;
        }
        int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
        while (iMin <= iMax) {
            int i = (iMin + iMax) / 2;
            int j = halfLen - i;
            if (i < iMax && B[j-1] > A[i]){
                iMin = i + 1; // i is too small
            }
            else if (i > iMin && A[i-1] > B[j]) {
                iMax = i - 1; // i is too big
            }
            else { // i is perfect
                int maxLeft = 0;
                if (i == 0) { maxLeft = B[j-1]; }
                else if (j == 0) { maxLeft = A[i-1]; }
                else { maxLeft = Math.max(A[i-1], B[j-1]); }
                if ( (m + n) % 2 == 1 )  return maxLeft; 

                int minRight = 0;
                if (i == m) { minRight = B[j]; }
                else if (j == n) { minRight = A[i]; }
                else { minRight = Math.min(B[j], A[i]); }

                return (maxLeft + minRight) / 2.0;
            }
        }
        return 0.0;
    }
}