每日小结

1. 对于vector容器，可以使用[]进行访问，很方便
2. 善于使用STL的函数方法，比如sort
3. 哈希表使用unordered_set，找不到时返回的是s.end()
4. 动态规划5要素：

1. 状态定义
2. 转移方程
3. 初始状态
4. 返回值
5. 简化空间复杂度（数组-->一个或简单几个变量）

217. 存在重复元素

给定一个整数数组，判断是否存在重复元素。

如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。

// 暴力双循环严重超时！不要这么做
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        int len = nums.size();
        if (len <= 1) return false;
        for (int i = 0; i < len; ++i) {
            for (int j = i+1; j < len; j++)
            {
                if (nums.at(i) == nums.at(j)) return true;
            }
        }
        return false;
    }
};

// 方法一：先排序，后查找
bool containsDuplicate(vector<int>& nums) {
        int len = nums.size();
        sort(nums.begin(), nums.end());  //加强对STL的使用
        for (int i = 0; i < len-1; i++)
        {
            if (nums[i] == nums[i + 1]) return true;  // 容器可以这么访问[]
        }
        return false;
    }

// 方法二：使用哈希表
bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> s;
        for (int i : nums) {
            if (s.find(i) != s.end()) return true;
            s.insert(i);
        }
        return false;
    }

53. 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

// 暴力法，能ac
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int len = nums.size();

        int max = nums[0];
        for (int i = 0; i < len; i++)
        {
            int temp = 0;
            for (int j = i; j < len; j++)
            {
                temp += nums[j];
                if (temp > max) max = temp;
            }
        }
        return max;
    }
};

动态规划5要素：

1. 状态定义
2. 转移方程
3. 初始状态
4. 返回值
5. 简化空间复杂度（数组-->一个或简单几个变量）

// 动态规划
int maxSubArray(vector<int>& nums) {
        int len = nums.size();
        int max = INT_MIN;
        int dp(nums[0]);  //简化只使用1个int
        max = dp;

        for (int i = 1; i < len; i++)
        {
            dp = dp + nums[i] > nums[i] ? dp + nums[i] : nums[i];
            max = dp > max ? dp : max;
        }
        return max;
    }

方法:3：贪心
方法4：分治，线段树（有点难，留着以后有时间回来做）