🕺作者: 主页
我的专栏 C语言从0到1 探秘C++ 数据结构从0到1 探秘Linux 算法题上机准备 😘欢迎 ❤️关注 👍点赞 🙌收藏 ✍️留言
题目
给定一个顺序表L和一个整数目标值target,请你设计一个时间复杂度尽可能高效的算法,在该顺序表中找出是否存在有两个元素之和等于target,若存在返回true否则返回false, 假设顺序表L中的元素值均在(0 - 1000之间).
算法思路
-
思路1暴力求解时间复杂度O(n²)
-
思路2用空间换时间,时间复杂度O(n),本质上类似哈希
题解
//思路1暴力求解时间复杂度O(n²)
bool twoSum(SqList L, int target) {for (int i = 0; i < L.length; i++) {for (int j = 0; j < L.length; j++) {if (i != j && L.data[i] + L.data[j] == target) {return true;}}}return false;
}
//思路2用空间换时间,时间复杂度O(n)
bool twoSum2(SqList L, int target) {int arr[1001] = { 0 };for (int i = 0; i < L.length; i++) {arr[L.data[i]] = 1;}for (int i = 0; i < L.length; i++) {int ans = target - L.data[i];if (arr[ans] == 1) {return true;}}return false;
}