[STLC++Map]checkSum

Bài tập.

Cho mỗi dãy số nguyên và một dãy số nguyên arr và một số nguyên dương sum.

Hãy kiểm tra xem dãy số có tồn tại hai số có tổng bằng sum hay không.

Ví dụ:

• Với arr = [2,4,-1,9,8], sum = 6 thì checkSum(arr, sum) = true.
  
  
• Với arr = [2,5,3,8,9], sum = 3 thì checkSum(arr, sum) = false.
  
  
• Với arr = [4,7,3,5], sum = 6 thì checkSum(arr, sum) = false.

Hướng dẫn.

Bài này nhiều bạn có thể dùng hai vòng for nhưng như thế độ phức tạp sẽ lên O(n^2), trong khi nếu bạn nghĩ tới map, nó có thể đưa độ phức tạp về O(n).

Sử dụng hàm find() để kiểm tra sự xuất hiện.

Code mẫu:

bool checkSum(vector<int> arr, int sum){
    map<int, int> mp;
    for (auto x : arr)
        mp[x]++;
    for (auto x : arr)
    {
        if (mp[sum-x] >= 1)
        {
            if (x != sum-x || (x == sum-x && mp[x] > 1))
                return true;
        }
    }
    return false;
}