【Leetcode做题记录】1.两数之和,2.两数相加,3. 无

1.两数之和

官方解答链接：
https://leetcode-cn.com/problems/two-sum/solution/

思路1

一开始思路就是暴力

时间复杂度：O(n^2)， 对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 O(n) 的时间。因此时间复杂度为 O(n^2)。
空间复杂度：O(1)。

思路2

遍历数组其余部分时使用map来使这部分时间复杂度变为O(1)
map的key是数组的值，value是数组的下标

2. 两数相加

题目描述及官方解答：
https://leetcode-cn.com/articles/add-two-numbers/

思路
即使用基本的数学方法，用指针依次指向两数的个位，十位等。
并用一个变量来存储进位。

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummyHead = new ListNode(0);
    //三个指针，指向当前计算的位数
    ListNode p = l1, q = l2, curr = dummyHead;
    //进位
    int carry = 0;
    //只要任意一个数还有下一位值
    while (p != null || q != null) {
        
        int x = (p != null) ? p.val : 0;
        int y = (q != null) ? q.val : 0;
        int sum = carry + x + y;
        //计算进位
        carry = sum / 10;
       //取余
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        if (p != null) p = p.next;
        if (q != null) q = q.next;
    }
    if (carry > 0) {
        curr.next = new ListNode(carry);
    }
    return dummyHead.next;
}

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

题目描述及官方解答：
https://leetcode-cn.com/articles/longest-substring-without-repeating-characters/

思路1:暴力

即判断所有子串是否含有重复字符
判断是否含有重复字符的方法是使用Set

思路2:滑动窗口

在判断区间[i,j)后的区间[i,j+1)是否含有重复元素时，不必重新判断，只需判断 第j元素是否存在于[i,j)区间即可

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);
            }
          //如果包含，i 前移 ，且移出set
            else {
                set.remove(s.charAt(i++));
            }
        }
        return ans;
    }
}

思路3:滑动窗口

当滑动窗口的下一个元素与区间内的重复，i 可直接跳到该下一个元素