题目

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

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 

子串

 的长度。

示例 1:

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

示例 2:

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

示例 3:

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

提示：

• 0 <= s.length <= 5 * 104
• s 由英文字母、数字、符号和空格组成

解答

滑动窗口的思路

class Solution {
    func lengthOfLongestSubstring(_ s: String) -> Int {
        var charMap: [Character: Int] = [:]
        var start = 0
        var maxLength = 0

        let count = s.count
        
        for i in 0..<count {
            // 1、取出当前字符
            let char = s[s.index(s.startIndex, offsetBy: i)]

            // 2、如果这个字符已经在字典里，取出他上次的位置，更新起点为上次出现的位置的后面
            if let lastIndex = charMap[char], start <= lastIndex {
                start = lastIndex + 1
            }

            // 3、更新到字典里
            charMap[char] = i

            // 4、计算新的长度为当前index-起点，并更新长度
            maxLength = max(maxLength, i - start + 1)

        }

        return maxLength
    }
}

题目

2. 两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

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

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

• 每个链表中的节点数在范围 [1, 100] 内
• 0 <= Node.val <= 9
• 题目数据保证列表表示的数字不含前导零

解答

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        /*
        哑：哑节点开头，哑节点固定，结果返回哑节点的后继
        标：标识两个遍历的节点和一个生成的新节点
        移：while循环向前走
        进：无法移动后再处理进位
        */
        let dummyHead = ListNode()
        var currentNode = dummyHead
        var carry = 0

        var p = l1
        var q = l2

        while p != nil || q != nil {
            /*
            只要不是都走到尽头，都要进入这里
            */
            let pValue = p?.val ?? 0
            let qValue = q?.val ?? 0
            var sum = pValue + qValue + carry

            // 1、是否要进位
            carry = sum / 10
            // 2、新节点的后继（value为当前相加取余）
            currentNode.next = ListNode(sum % 10)

            // 3、往后移动
            currentNode = currentNode.next!
            p = p?.next
            q = q?.next
        }

        /*
        两个单链表都走到尽头了，如果存在进位，要追加一个后继
        这个节点的value只能是1，实际是最高位
        */
        if carry > 0 {
            currentNode.next = ListNode(carry)
        }

        return dummyHead.next
        
    }
}

题目

1. 两数之和

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

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 只会存在一个有效答案

题解

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        /*
        从头开始遍历，看剩下的数里是否有相加等于目标数
        时间复杂度: O(n2)
        优化：
            遍历一次数组，生成一个字典[int: int]，
            valueForKey来找index
        */

        let count = nums.count
        if count == 0 {
            return []
        }
        for index in 0..<count {
            let currentValue = nums[index]
            for targetIndex in 0..<count {
                if index == targetIndex {
                    continue
                }
                let targetValue = nums[targetIndex]
                if currentValue + targetValue == target {
                    return [index, targetIndex]
                }
            }
        }
        return []
    }
}