algorithm weekly ~ 2022.02.06

217. Contains Duplicate

Contains Duplicate - LeetCode

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

O(n long n) + O(n)

bool containsDuplicate(vector<int>& nums) {
	sort(nums.begin(), nums.end());
	
	for(int i = 1; i < nums.size(); i++) {
		if (nums[i-1] == nums[i]) {
			return true;
		}
	}
	
	return false;
}

 

unordered_map 사용

bool containsDuplicate(vector<int>& nums) {
	
	unordered_map<int, int> m;
	for (auto a:nums) {
		if (m.count(a) == false) {
			m[a];
		}
		else { 
			return true;
		}
	}
	
	return false;
}

---

 

39. Combination Sum

Combination Sum - LeetCode

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

class Solution {
public:
    void rec(vector<int>& candidates, vector<int>& arr, int target, int num) {
        if (target == 0) {
            result.push_back(arr);
        }
        else if (target < 0) {
            return ;
        }
        else {
            for(int i = num ; i < candidates.size(); ++i) {
                arr.push_back(candidates[i]);
                rec(candidates, arr, target - candidates[i], i);
                arr.pop_back();
            }
        }
    }
    vector<vector<int>> result;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<int> arr;
        rec(candidates, arr, target, 0);
        return result;
    }
};