#
Problem
By
blackntt
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;
}