求数组中两两相加等于20的组合(Python实现),数组可以直接相加吗,题目求数组中两两相加
求数组中两两相加等于20的组合(Python实现),数组可以直接相加吗,题目求数组中两两相加
题目
求数组中两两相加等于20的组合。
例:给定一个数组[1, 7, 17, 2, 6, 3, 14],这个数组中满足条件的有两对:17+3=20, 6+14=20。
解析
分为两个步骤:
先采用堆排序或快速排序对数组进行排序,时间复杂度为O(nlogn)。然后对排序的数组分别从前到后和从后到前进行遍历, 时间复杂度为O(n)。假设从前到后遍历的下标为begin,从后到前遍历的下标为end。
当arr[begin] + arr[end] < 20时,满足条件的数一定在[begin+1, end]之间;当arr[begin] + arr[end] > 20时,满足条件的数一定在[begin, end-1]之间;当arr[begin] + arr[end] = 20时,找到一组符合条件的数,剩下的组合一定在[begin-1, end-1]之间。整个算法的时间复杂度为O(nlogn)。
Python实现
# -*- coding:utf-8 -*-def quick_sort(arr, left, right): """快速排序""" if left >= right: return low = left high = right p = arr[left] while left < right: while left < right and arr[right] >= p: right -= 1 arr[left] = arr[right] while left < right and arr[left] <= p: left += 1 arr[right] = arr[left] arr[left] = p quick_sort(arr, low, left-1) quick_sort(arr, left+1, high)def find_sum(arr, sum): """寻找数组中相加等于sum的组合""" quick_sort(arr, 0, len(arr) - 1) begin, end = 0, len(arr) - 1 while begin < end: if arr[begin] + arr[end] < sum: begin += 1 elif arr[begin] + arr[end] > sum: end -= 1 else: print(‘%s %s‘ % (arr[begin], arr[end])) begin += 1 end -= 1if __name__ == ‘__main__‘: arr = [1, 7, 17, 2, 6, 3, 14] find_sum(arr, 20)
参考资料
《Java程序员面试笔试宝典》求数组中两两相加等于20的组合(Python实现)
评论关闭