3/11题解

1.给你一个整数数组 A，只有可以将其划分为三个和相等的非空部分时才返回 true，否则返回 false。
形式上，如果可以找出索引 i+1 < j 且满足 (A[0] + A[1] + ... + A[i] == A[i+1] + A[i+2] + ... + A[j-1] == A[j] + A[j-1] + ... + A[A.length - 1]) 就可以将数组三等分。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-array-into-three-parts-with-equal-sum

class Solution {
public:
    bool canThreePartsEqualSum(vector<int>& A) {
        int sum=0;
         for(int i=0;i<A.size();i++)
         {
             sum+=A[i];
         }
         if(sum%3!=0) return false;//数组里所有数的和应该被三整除
         int avg=sum/3;//三等分
         int count=0,cur=0;//从前往后遍历，找到等于三等分的就count++
         for(int i=0;i<A.size();i++)
         {
             cur+=A[i];
             if(cur==avg)
             {
                 count++;
                 cur=0;
             }
             if(count==2&&(i!=A.size()-1))//为了防止[1,-1,1,-1]这样的测试用例
             {
                 return true;
             }
         }
         return false;     
    }
};

2.给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int,int> m;
        for(int i=0;i<nums.size();i++)
        {
            m[nums[i]]=i; //key值是数组的值，value是数组的下标     
        }
        for(int i=0;i<nums.size();i++)
        {
            if(m.find(target-nums[i])!=m.end()&&m[target-nums[i]]!=i)
              return {i,m[target-nums[i]]};//如果找到符合的key，就找这个key对应的value，返回value和i
        }
        return {};
    }
};