提高代码效率 - ChatGPT应用实例

为Python代码的效率提升提供想法。

提示

系统 
你将会得到一段Python代码，你的任务是提供提升效率的想法。 
用户 
from typing import List 
                        
def has_sum_k(nums: List[int], k: int) -> bool: 
   """ 
   如果在nums中有两个不同的元素使得它们的和等于k，则返回True，否则返回False。 
   """ 
   n = len(nums) 
   for i in range(n): 
       for j in range(i+1, n): 
           if nums[i] + nums[j] == k: 
               return True 
   return False

样例回复

当前实现的时间复杂度是O(n^2)，因为有两层for循环。我们可以通过使用一个集合来存储我们已经看到的数字，将它改进为O(n)。

这是改进后的代码：

```python 
from typing import List

def has_sum_k(nums: List[int], k: int) -> bool: 
   """ 
   如果在nums中有两个不同的元素使得它们的和等于k，则返回True，否则返回False。 
   """ 
   seen = set() 
   for num in nums: 
       if k - num in seen: 
           return True 
       seen.add(num) 
   return False 
```

在这段代码中，我们只遍历一次数字列表。对于每个数字，我们检查它的补数（k - num）是否在我们已经看到的数字的集合中。如果在，我们返回True，因为我们找到了两个和为k的数字。如果不在，我们把当前的数字加入到集合中，然后继续下一个数字。如果我们遍历完列表都没有找到两个和为k的数字，我们就返回False。

这种方法将时间复杂度从O(n^2)降低到了O(n)，对于大列表来说，这是一个显著的改进。空间复杂度也是O(n)，因为在最坏的情况下，我们可能需要把所有的数字都存到集合中。然而，这是为了提高时间复杂度而做的合理的权衡。

API请求

{ 
 "model": "gpt-4", 
 "messages": [ 
   { 
     "role": "system", 
     "content": "You will be provided with a piece of Python code, and your task is to provide ideas for efficiency improvements." 
   }, 
   { 
     "role": "user", 
     "content": "from typing import List\n            \n            \ndef has_sum_k(nums: List[int], k: int) -> bool:\n    \"\"\"\n    Returns True if there are two distinct elements in nums such that their sum \n    is equal to k, and otherwise returns False.\n    \"\"\"\n    n = len(nums)\n    for i in range(n):\n        for j in range(i+1, n):\n            if nums[i] + nums[j] == k:\n                return True\n    return False" 
   } 
 ], 
 "temperature": 0, 
 "max_tokens": 1024 
}

来源：Improve code efficiency

• 添加新评论