黑马程序员技术交流社区

标题: 一道面试题 [打印本页]

---

作者: t_mac    时间: 2011-12-11 22:44
标题: 一道面试题
数组int[] arr={3,5,2,4,1,8}，要求从arr中找出所有“和”等于10的子集。

除了简单的循环遍历外，大家有什么高效的方法吗？

---

作者: 唐秀启    时间: 2011-12-11 22:51


先排序，然后再查找，如果大于了 下面的就不用加了，
继续找第二个往下加。。
要断电了
没法写代码了

---

作者: wsssx    时间: 2011-12-12 11:27
提示: 作者被禁止或删除 内容自动屏蔽

---

作者: 程传鹏    时间: 2011-12-12 11:44


数组int[] arr={3,5,2,4,1,8}，要求从arr中找出所有“和”等于10的子集。

除了简单的循环遍历外，大家有什么高效的方法吗？
  当仅为求两个数的和时，如下分析
  解答
  1.另外设个布尔数组，arrb,arrb表示为数值为i的数值是否存在，如arrb[3]为true，arrb[9]为false
  2.通过arr数组确定arrb数组的真假值
  3.循环，判断所要求的和即10-arr[j]=x的结果在arrb数组中是真还是假，即判断arrb[x],若是真，输出这两个数，并把arrb[x]改成false，否，循环判断下一个数值x
  该方法的优点：只进行一次循环即可得到结果
  但当求若干个数的和的时候，怎么办？
  优化：
   我们直接优化第三步：
  3.循环，判断所要求的和即10-arr[j]=x的结果在arrb数组中是真还是假，即判断arrb[x],若是真，输出这两个数，并把arrb[x]改成false，否，则循环减后的这个数，若这个数可以被剩下的数相加得到，则表示10可以由x和arr[j]相加得到，虽然x数组中不存在，但是x可以由剩下的数相加得到，到此，就把问题变成了 判断10=判断x+arr[j];用递归或递推方法都可以实现.

---

作者: 程传鹏    时间: 2011-12-12 11:58
不知道为什么，字体成这样了

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2