博客

1.两数之和

描述：给定一个整数数组

nums

和一个目标值

target

，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

暴力循环

没啥好说的，最容易想到的逻辑，时间复杂度O(n2)

双指针

排序后，利用双指针向中间逼近，知道找到目标值，时间复杂度O(nlogn)

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int left = 0, right = numbers.size() - 1;
        while (left < right)
        {
            if (numbers[left] + numbers[right] < target)
                left++;
            else if (numbers[left] + numbers[right] > target)
                right--;
            else
                return vector<int>{left + 1, right + 1};
        }
        return {};
    }
};

一遍字典

对于当前元素x，与之匹配的另一数字为target-x，我们每遍历一个x，都将target-x作为key添加到字典中，其值为下标，在之后的遍历过程中，一旦发现当前x已存在字典中，说明之前已经找到匹配的元素，然后字典返回其下标。时间复杂度O(n)

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ret = { -1, -1 };
		map<int, int> m;
		for (int i = 0; i < nums.size(); i++)
		{
			int pair = target - nums[i];
			int x = m[pair];
			if (m[pair])
			{
				ret[0] = m[pair] - 1; ret[1] = i;
				return ret;
			}
            m[nums[i]] = i + 1;
		}
		return ret;
    }
};

2.两数相加

描述：给出两个

非空

的链表用来表示两个非负的整数。其中，它们各自的位数是按照

逆序

的方式存储的，并且它们的每个节点只能存储

一位

数字。

这题熟悉链表的话还是很容易实现吧，稍微得注意下进位问题

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int car = 0;
        ListNode* res = NULL;
        ListNode* p0 = res;
        ListNode* p1 = l1;
        ListNode* p2 = l2;
        while (p1 != NULL && p2 != NULL)
        {
            if (!res)
            {
                res = new ListNode((p1->val + p2->val + car) % 10);
                p0 = res;
            }
            else
            {
                p0->next = new ListNode((p1->val + p2->val + car) % 10);
                p0 = p0->next;
            }
            if (p1->val + p2->val + car >= 10)
                car = 1;
            else
                car = 0;
            p1 = p1->next;
            p2 = p2->next;
        }
        while (p1)
        {
            p0->next = new ListNode((p1->val + car) % 10);
            if (p1->val + car >= 10)
                car = 1;
            else
                car = 0;
            p1 = p1->next;
            p0 = p0->next;
        }
        while (p2)
        {
            p0->next = new ListNode((p2->val + car) % 10);
            if (p2->val + car >= 10)
                car = 1;
            else
                car = 0;
            p2 = p2->next;
            p0 = p0->next;
        }
        if (car == 1)
            p0->next = new ListNode(1);
        return res;
    }
};

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

描述：给定一个字符串，请你找出其中不含有重复字符的

最长子串

的长度。

解决该问题可以使用滑动窗口模型。我们维护一个滑动窗口，并限制其中的字符集不可重复，每次滑动窗口进行扩张，若出现重复则收缩窗口。在具体实现中，我们可以用两个下标来作为滑动窗口的边界，以一个字典来维护字符集。然后保存出现过的最大长度。

如何收缩窗口有两种策略，这与我们的字典有关。

若字典的值为bool型，即我们只关心该字符是否存在，则左边界每次向右收缩一个单位，每次收缩都去除掉某个字符，直到右边界扩张进的新字符没有出现过为止。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        map<int, int> m;
        int left = 0, right = -1;
        int res = 0;
        for (int i = 0; i < s.length(); i++)
        {
            if (m[s[i]])
            {
                m[s[left]] = false;
                left++;
                i--;
                continue;
            }
            right++;
            m[s[i]] = true;
            res = max(res, right - left + 1);
        }
        return res;
    }
};

若字典的值为某个字符出现的下标，则我们每次收缩都收缩到该下标+1处。若这个下标比左边界小，则收缩到左边界+1

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        map<int, int> m;
        int left = 0, right = 0;
        int res = 0;
        for (int i = 0; i < s.length(); i++)
        {
            if (m[s[i]] && m[s[i]] > left)
                left = max(left + 1, m[s[i]]);
            right = i;
            m[s[i]] = i + 1;
            res = max(res, right - left + 1