1.两数之和

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

分析：普通方法下，我们可以进行两次for循环遍历。第一次遍历得到目标值减去第一个数的值n，在第一个for内嵌套第二个for循环，找到数组剩下的数中等于n的下标。

vector<int> twoSum(vector<int> &nums, int target) {
    vector<int> res;
    for(int i = 0; i < nums.size(); i++) {
        int n = target - nums[i];
        for(int j = i + 1; j < nums.size(); j++) {
            if(n == nums[j]) {
                res.push_back(i);
                res.push_back(j);
                return res;
            }
        }
    }
}

另一种方法是利用hashmap，在for循环内，每一次遍历用目标值减去当前数组元素的值得到结果n，然后在map中查找是否存在key为n的元素，如果不存在，将当前元素按<值，下标>的形式存入map，如果存在，将当前元素的下标和map中n对应的下标存入vector并返回。

vector<int> twoSum(vector<int> &nums, int target) {
      std::map<int, int> M;
      for(int i = 0; i < nums.size(); ++i) {
          int n = target - nums[i];
          if (M.find(n) != M.end()) {
              vector<int> res(M[n], i);
              return res
          }else {
              M[nums[i]] = i;
          }
      }
}

2.两数相加

给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。

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

分析：这道题其实就是遍历两个链表并将每个对应结点的值相加构成一个新的链表的过程。同时在这个过程中，我们需要考虑到一下几个问题：

• 结点值大于10的进位。

• 链表长度不同时的遍历判断

• 最后一位也大于10时要新增一个结点

  ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
      int carry = 0;    //用carry保存进位，并初始化为0
      ListNode *res = (ListNode *)malloc(sizeof(ListNode));    //创建一个新的链表保存相加结果。
      ListNode *cur = res;    //再声明一个链表用于遍历保存结点。
      while(l1 != NULL || l2 != NULL) {    //while循环只有当两个链表都为空的时候停止。
        int v1 = (l1 == NULL) ? 0 : l1->val;    //l1为空时v1为0，否则为l1的值
        int v2 = (l2 == NULL) ? 0 : l2->val;  //l2为空时v2为0，否则为l2的值
        int sum = v1 + v2 + carry;    //相加结果
        ListNode *node = new ListNode(sum%10); //生成一个结点，值为和模10。
        cur->next = node;
        cur = cur->next;    // 将当前结点的next指向node，然后将当前结点指向结点的下一个结点。
        carry = sum/10;    // 保存进位
        if (l1 != NULL) l1 = l1->next;
        if (l2 != NULL) l2 = l2->next;      //遍历下一个结点
      }
      if(carry == 1) {    //如果还有进位，添加一个新结点
        ListNode *node = new ListNode(1);
        cur->next = node;
      }
      return res->next;  // 因为结果链表头为空，所以要返回从下一个结点开始的链表。
  }
  

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

给定一个字符串，找出不含有重复字符的最长子串的长度。

示例：
给定 "abcabcbb" ，没有重复字符的最长子串是 "abc" ，那么长度就是3。
给定 "bbbbb" ，最长的子串就是 "b" ，长度是1。
给定 "pwwkew" ，最长子串是 "wke" ，长度是3。请注意答案必须是一个子串，"pwke" 是 子序列 而不是子串。

分析：要找到无重复的最长子串，其实就是找到两个重复字符之间的长度。但是这里要注意一个问题，就是重复字符之间可能还有其他重复字符，所以我们用一个变量来保存最近一次重复字符的位置，记作start。然后判断start与当前保存的重复字符的位置大小，如果start小于当前的重复字符位置，则令start等于当前重复字符位置，否则不变。

    int lengthOfLongestString(string s) {
      map<char, int> m;      //map保存字符所在位置
      int length = 0;             //当前的最长长度
      int start = 0;                //最近一次重复字符位置
      for(int i = 0; i < s.length(); ++i) {  //循环遍历字符串
        if(m.find(s[i]) != m.end()) {  //查找当前字符是否有重复
          start = m[s[i]] > start ? m[s[i]] : start;  //start小于当前字符重复位置，更新start
        }
        length = length > (i - start + 1) ? length : (i - start + 1);  //当前无重复子串长度与之前保存的最长子串长度比较并更新长度。
        m[s[i]] = i + 1;  //保存当前字符位置
      }
      return length;
    }

4.两个排序数组的中位数

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。

请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。

示例 1:
nums1 = [1, 3]
nums2 = [2]
中位数是 2.0

示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
中位数是 (2 + 3)/2 = 2.5

分析：要找到两个数组的中位数，首先我们想到的就是把两个数组合并为一个数组，这样就可以很方便的找到中位数了。 由于给出的两个数组是有序的，而且要求算法时间复杂度为O(log(m+n))。我们很容易就想到归并排序的合并方法。

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
      int m = 0, n = 0; 声明分别对应两个数组下标的变量。
      vector<int> merge;
      while(m < nums1.size() && n < nums2.size()) {    //m,n都符合条件时进入while循环
        if(nums1[m] < nums2[n]) {    //比较nums1[m] 与nums2[n]的大小，将小的存入合并数组
          merge.push_back[nums1[m]];
          m++;
        } else {
          merge.push_back[nums2[n]];
          n++;
        }
      }

      // 将剩下的元素添加都数组 下面两个循环最多只会进入一个 或者两个都不会进入。所以时间复杂度不会超过m+n
      while(m < nums1.size()) {
        merge.push_back[nums1[m]];
        m++;
      }
      while(n < nums2.size()) {
          merge.push_back[nums2[n]];
          n++;
      }
      
      int s = merge.size();
      if (s%2 == 0) return double(merge[s/2] + merge[s/2 - 1]) / 2.0;
      return merge[s/2];
    }

5.最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。

示例 1：
输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。

示例 2：
输入: "cbbd"
输出: "bb"

分析：回文字符串就是从中心点往两边遍历的所有对称点字符串都相同，根据这种特性，我们可以以字符串的每个字符为中心点找到对应的回文字符串，然后获取最长的一个即为最长回文子串。这里要考虑两种情况：1.子串为奇数。2.子串为偶数。

    string longestPalindrome(string s) {
      int start = 0, maxLen = 0; //保存最长子串的起始位置以及长度。
      for(int m = 0; m < s.length(); ++m) {
        int l1 = longestSubString(s, m, m) //奇数情况，以自身为中心
        int l2= longestSubString(s, m, m+1) //偶数情况，以自身与下一个字符的中点为中心
        int len = l1>l2 ? l1 : l2;  //  当前字符的最长回文子串
        if(len > maxLen) {
          //当前长度大于之前保存的最长子串
          maxLen = len;
          start = m - (len - 1) / 2; //保存当前长度，更新起始位置。不管奇偶，(len-1)/2得到的总是当前字符到起始点的距离。
        }
        return s.substr(start, maxLen);
      }
    }

    int longestSubString(string s, int l, int r) {
    //从中心往两边扩展获取回文子串
      while(l >= 0 && r < s.length() && s[l] = s[r]) {
        l--;
        r--;
      }
      return r-l-1;  //子串长度 由于最后一次进入while的时候，左右各自多扩展了1位，所以造成长度多了2，但是子串长度包含起始位置自身要+1。 原始式子为 (r-l+1-2) 简化为(r-l-1)。
    }