1. 两数之和

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例:

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

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

解答:

  • 暴力法

暴力法很简单,遍历每个元素 xx,并查找是否存在一个值与 target - xtarget−x 相等的目标元素。

public class Solution1 {
    public int[] twoSum(int[] nums,int target) {
        int result[] = new int[2];
        for (int i = 0; i < nums.length; i++) {
            int num1 = nums[i];
            int num2 = target - num1;
            for (int j = 0; j < nums.length; j++) {
                if(num2==nums[j]&&i!=j){
                    result[0] = i;
                    result[1] = j;
                }
            }
        }
        return result;
    }
}
  • 两遍哈希表
为了对运行时间复杂度进行优化,我们需要一种更有效的方法来检查数组中是否存在目标元素。如果存在,我们需要找出它的索引。保持数组中的每个元素与其索引相互对应的最好方法是什么?哈希表。

通过以空间换取速度的方式,我们可以将查找时间从 O(n)O(n) 降低到 O(1)O(1)。哈希表正是为此目的而构建的,它支持以 近似 恒定的时间进行快速查找。我用“近似”来描述,是因为一旦出现冲突,查找用时可能会退化到 O(n)O(n)。但只要你仔细地挑选哈希函数,在哈希表中进行查找的用时应当被摊销为 O(1)O(1)。

一个简单的实现使用了两次迭代。在第一次迭代中,我们将每个元素的值和它的索引添加到表中。然后,在第二次迭代中,我们将检查每个元素所对应的目标元素(target - nums[i]target−nums[i])是否存在于表中。注意,该目标元素不能是 nums[i]nums[i] 本身!
public int[] twoSumSecond(int[] nums, int target){
        int[] result = new int[2];
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            int num1 = nums[i];
            int num2 = target - num1;
            if(map.containsKey(num2)&&map.get(num2)!=i){
                result[0] = i;
                result[1] = map.get(num2);
            }
        }
        return result;
    }
  • 一遍哈希表
事实证明,我们可以一次完成。在进行迭代并将元素插入到表中的同时,我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在,那我们已经找到了对应解,并立即将其返回。
public int[] twoSumThird(int[] nums, int target){
        int[] result = new int[2];
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int num1 = nums[i];
            int num2 = target - num1;
            if(map.containsKey(num2)&&map.get(num2)!=i){
                result[0] = i;
                result[1] = map.get(num2);
            }
            map.put(nums[i], i);
        }
        return result;
    }

复杂度

  • 暴力法
    • 时间复杂度:O(n^2)对于每个元素,我们试图通过遍历数组的其余部分来寻找它所对应的目标元素,这将耗费O(n)的时间。因此时间复杂度为O(n^2)。
    • 空间复杂度:O(1)。
  • 两遍哈希表
    • 时间复杂度:O(n),我们把包含有 n 个元素的列表遍历两次。由于哈希表将查找时间缩短到 O(1) ,所以时间复杂度为 O(n)。
    • 空间复杂度:O(n),所需的额外空间取决于哈希表中存储的元素数量,该表中存储了 n 个元素。
  • 一遍哈希表
    • 时间复杂度:O(n),我们只遍历了包含有 n 个元素的列表一次。在表中进行的每次查找只花费 O(1) 的时间。
    • 空间复杂度:O(n),所需的额外空间取决于哈希表中存储的元素数量,该表最多需要存储 n 个元素。

2. 两数相加

给出两个非空的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。

如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例:

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

解答
伪代码如下:

  • 将当前结点初始化为返回列表的哑结点。
  • 将进位 carrycarry 初始化为 00。
  • 将 pp 和 qq 分别初始化为列表 l1l1 和 l2l2 的头部。
  • 遍历列表 l1l1 和 l2l2 直至到达它们的尾端。
    • 将 xx 设为结点 pp 的值。如果 pp 已经到达 l1l1 的末尾,则将其值设置为 00。
    • 将 yy 设为结点 qq 的值。如果 qq 已经到达 l2l2 的末尾,则将其值设置为 00。
    • 设定 sum = x + y + carrysum=x+y+carry。
    • 更新进位的值,carry = sum / 10carry=sum/10。
    • 创建一个数值为 (sum \bmod 10)(summod10) 的新结点,并将其设置为当前结点的下一个结点,然后将当前结点前进到下一个结点。
    • 同时,将 pp 和 qq 前进到下一个结点。
  • 检查 carry = 1carry=1 是否成立,如果成立,则向返回列表追加一个含有数字 11 的新结点。
  • 返回哑结点的下一个结点。
public class Solution2 {
    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
        }
    }
    public ListNode addTwoNumbersFirst(ListNode l1, ListNode l2) {
        ListNode result = new ListNode(0);//初始化一个为0的节点
        int carry = 0;//定义一个进位标识
        ListNode sumNode = result;
        while (l1!=null||l2!=null||carry!=0) {
            int num1 = l1==null?0:l1.val;
            int num2 = l2==null?0:l2.val;
            int sum = num1+num2+carry;
	    carry = sum/10;
            int resultNum = sum%10;
            ListNode listNode = new ListNode(resultNum);
            sumNode.next = listNode;
            sumNode = listNode;
            if(l1!=null){l1 = l1.next;}
            if(l2!=null){l2 = l2.next;}
        }
        return result.next;
    }
}

复杂度分析

  • 时间复杂度:O(max(m,n)),假设 mm 和 nn 分别表示 l1l1 和 l2l2 的长度,上面的算法最多重复max(m,n) 次。
  • 空间复杂度:O(max(m,n)), 新列表的长度最多为max(m,n)+1。

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

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

示例1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是子串的长度,"pwke" 是一个子序列,不是子串。

解答

  • 方法一:暴力法
    • 思路
      逐个检查所有的子字符串,看它是否不含有重复的字符。

    • 算法
      假设我们有一个函数 boolean allUnique(String substring) ,如果子字符串中的字符都是唯一的,它会返回 true,否则会返回 false。 我们可以遍历给定字符串 s 的所有可能的子字符串并调用函数 allUnique。 如果事实证明返回值为 true,那么我们将会更新无重复字符子串的最大长度的答案。

    • 现在让我们填补缺少的部分:

      • 为了枚举给定字符串的所有子字符串,我们需要枚举它们开始和结束的索引。假设开始和结束的索引分别为 ii 和 jj。那么我们有 0 \leq i \lt j \leq n0≤i<j≤n(这里的结束索引 jj 是按惯例排除的)。因此,使用 ii 从 0 到 n - 1n−1 以及 jj 从 i+1i+1 到 nn 这两个嵌套的循环,我们可以枚举出 s 的所有子字符串。
      • 要检查一个字符串是否有重复字符,我们可以使用集合。我们遍历字符串中的所有字符,并将它们逐个放入 set 中。在放置一个字符之前,我们检查该集合是否已经包含它。如果包含,我们会返回 false。循环结束后,我们返回 true。
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int result = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i+1; j < s.length()+1; j++) {
                if (allUnique(s,i,j)) {
                    result = Math.max(j-i, result);
                }
            }
        }
        return result;
    }
    public static boolean allUnique(String s, int start, int end) {
        Set<Character> set = new HashSet<>();
        for (int i = start; i < end; i++) {
            if(set.contains(s.charAt(i))){return false;}
            set.add(s.charAt(i));
        }
        return true;
    }
}
  • 方法二:滑动窗口
    • 通过使用 HashSet 作为滑动窗口,我们可以用 O(1)O(1) 的时间来完成对字符是否在当前的子字符串中的检查。
    • 滑动窗口是数组/字符串问题中常用的抽象概念。 窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合,即 [i, j)[i,j)(左闭,右开)。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。例如,我们将 [i, j)[i,j) 向右滑动 11 个元素,则它将变为 [i+1, j+1)[i+1,j+1)(左闭,右开)。
    • 回到我们的问题,我们使用 HashSet 将字符存储在当前窗口 [i, j)[i,j)(最初 j = ij=i)中。 然后我们向右侧滑动索引 jj,如果它不在 HashSet 中,我们会继续滑动 jj。直到 s[j] 已经存在于 HashSet 中。此时,我们找到的没有重复字符的最长子字符串将会以索引 ii 开头。如果我们对所有的 ii 这样做,就可以得到答案。
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int result = 0;
        int i=0,j=0;
        Set<Character> set = new HashSet<>();
        while(i<s.length()&&j<s.length()){
            //[i,j]
            if (!set.contains(s.charAt(j))) {
                set.add(s.charAt(j));
                j++;
                result = Math.max(j-i, result);
            }else{
                set.remove(s.charAt(i));
                i++;
            }
        }
        return result;
    }
}
  • 方法三:优化的滑动窗口
    上述的方法最多需要执行 2n 个步骤。事实上,它可以被进一步优化为仅需要 n 个步骤。我们可以定义字符到索引的映射,而不是使用集合来判断一个字符是否存在。 当我们找到重复的字符时,我们可以立即跳过该窗口。
    也就是说,如果 s[j]在 [i, j) 范围内有与 j' 重复的字符,我们不需要逐渐增加 i 。 我们可以直接跳过 [i,j']范围内的所有元素,并将 i 变为 j' + 1。
class Solution {
    public int lengthOfLongestSubstringThird(String s) {
        int result = 0;
        Map<Character,Integer> map = new HashMap<>();
        for (int i = 0,j=0; j < s.length(); j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(i, map.get(s.charAt(j)));
            }
            result = Math.max(j-i+1, result);
            map.put(s.charAt(j), j+1);
        }
        return result;
    }
}


标题:LeetCode算法解析(一)
作者:XxwGit
地址:http://xxwgit.cn/solo/articles/2019/12/23/1577065619822.html