当前位置: 首页> 财经> 创投人物 > 【顺序表】09 两个元素之和等于target

【顺序表】09 两个元素之和等于target

时间:2025/7/14 20:21:32来源:https://blog.csdn.net/m0_67759533/article/details/140103832 浏览次数:1次

🕺作者: 主页

我的专栏
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;
}
关键字:【顺序表】09 两个元素之和等于target

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: