two sum

1 两数之和

https://leetcode.cn/problems/two-sum/

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> m;
        vector<int> result;
        for(int i = 0; i < nums.size(); i++) {
            if(m.contains(target - nums[i])) {
                result.push_back(m[target - nums[i]]);
                result.push_back(i);
                return result;
            }
            m[nums[i]] = i;
        }
        return result;
        
    }
};

2.两数相加

https://leetcode.cn/problems/add-two-numbers/

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode();
        int cur = 0;
        ListNode* p = dummy;
        while(l1 || l2 || cur > 0) {
            int sum = cur;
            if(l1) {
                sum += l1 -> val;
                l1 = l1 -> next;
            }
            if(l2) {
                sum += l2 -> val;
                l2 = l2 -> next;
            }
           
            cur = sum / 10;
            int val = sum % 10;
            ListNode* node = new ListNode();
            node -> val = val;
            p -> next = node;
            p = p -> next;
       
        }
        return dummy -> next;

    }
};

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

https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int res = 0;

        unordered_set<char> set;

        for(int i = 0, j = 0; j < s.length();) {

            while(i < j && set.contains(s[j])) {
                set.erase(s[i]);
                i++;
            }
            set.insert(s[j++]);
            res = res > set.size() ? res : set.size();
            
        }

        return res;

        
    }
};

4.寻找两个正序数组的中位数

https://leetcode.cn/problems/median-of-two-sorted-arrays/description/

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {

        int allSize = nums1.size() + nums2.size();

        if(allSize & 1) {
            return findNth(nums1, nums2, allSize / 2 + 1, 0, 0);
        }

        int left = findNth(nums1, nums2, allSize / 2, 0, 0) ;
        int right = findNth(nums1, nums2, allSize / 2 + 1, 0, 0);

        return (left + right) / 2.0;
    }


    int findNth(vector<int>& nums1, vector<int>& nums2, int n, int i, int j) {

        if(nums1.size() <= i ) {
            return nums2[j + n - 1];
        }

        if(nums2.size() <= j) {
            return nums1[i + n - 1];
        }

        if(n == 1) {
            return nums1[i] >= nums2[j] ?  nums2[j] : nums1[i];
        }
        int mid = n /2 ;
        int l1 = mid;
        int l2 = n - mid;
        if(i + l1 - 1 >= nums1.size()) {
            l1 = nums1.size() - i;
            l2 = n - l1;
        }else if(l2 + j - 1 >= nums2.size()) {
            l2 = nums2.size() - j;
            l1 = n - l2;
        }

        if(nums1[i + l1 - 1] == nums2[j + l2 - 1]) {
            return nums1[i + l1 - 1];
        }

        if(nums1[i + l1 - 1] < nums2[j + l2 - 1]) {
            return findNth(nums1, nums2, n - l1, i + l1, j);
        }

        return findNth(nums1, nums2, n - l2, i, j + l2);

    }
};

5. 最长回文子串

https://leetcode.cn/problems/longest-palindromic-substring/description/

class Solution {
public:
    string longestPalindrome(string s) {
        if(!s.length()) {
            return "";
        }
        int left = 0;
        int right = 0;

        for(int i = 0; i < s.length(); i++) {
            int l = i - 1;
            int r = i + 1;
            while(l >= 0 && r < s.length() && s[l] == s[r]) {
                if(r - l + 1 > right - left + 1) {
                    left = l;
                    right = r;
                }
                l--;
                r++;
            }
            l = i; 
            r = i + 1;
            while(l >= 0 && r < s.length() && s[l] == s[r]) {
                if(r - l + 1 > right - left + 1) {
                    left = l;
                    right = r;
                }
                l--;
                r++;
            }
        }
        return substr(s, left, right);
    }

    string substr(string s, int i, int j) {
        string res = "";
        for(int k = i; k <= j; k++) {
            res += s[k];
        }
        return res;

    }
};