Menu Close

Bài toán tổng 2 số | two sum Problem

Problem

Cho mảng gồm các số nguyên. Tìm 2 phần tử mà tổng của chúng bằng một số cho trước. Giả sử rằng một phần tử không dùng 2 lần, và chỉ có 1 cặp số trong mảng thoả điều kiện về tổng. problem link

Solution

  • 1st solution:
    Với mỗi phần tử trong mảng thì duyệt toàn mảng tìm một phần tử khác trong mảng để tổng của chúng bằng target mong muốn.
    Time complexity: O(n^2)
vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        for (int i=0;i<nums.size()-1;i++){
            for(int j=i+1;j<=i+1;j++){
                if(nums[i]+nums[j]==target){
                    result.push_back(i);
                    result.push_back(j);
                    break;
                }
            }
        }
        return result;
}
  • 2nd solution
    Tương tự ý tưởng giải pháp 1, nhưng giải time complexity bằng hash table. Duyệt từng phần tử trong mảng rồi tìm một phần tử bù (tổng-giá trị phần tử đang xét) trong hash table để giải time complexity.
    Time complexity: gần O(n)
vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        map<int,int> hashMap;
        for(int i=0;i< nums.size();i++){
            hashMap[nums[i]]=i;
        }
        for(int i=0;i<nums.size();i++){
            map<int,int>::iterator it = hashMap.find(target-nums[i]);
            if(it!=hashMap.end()){
                result.push_back(i);
                result.push_back(it->second);
                break;
            }
        }
        return result;
    }
  • 3rd solution
    Tương tự giải pháp 2, nhưng tìm phần bù của số đang duyệt ngay trong vòng lặp tạo hash table.
    Time complexity: gần O(n) (tốt hơn giải pháp 2)
 vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        map<int,int> hashMap;
        for(int i=0;i< nums.size();i++){
            map<int,int>::iterator it = hashMap.find(target-nums[i]);
            if(it!=hashMap.end()){
                result.push_back(i);
                result.push_back(it->second);
                break;
            }
            hashMap[nums[i]]=i;
        }

        return result;
}

Leave a Reply

Your email address will not be published. Required fields are marked *