Create check_sum_of_square_numbers.py

yingl · web-flow · commit f6573e5ad6d4 · 2018-01-01T14:41:13.000+08:00
diff --git a/check_sum_of_square_numbers.py b/check_sum_of_square_numbers.py
@@ -0,0 +1,27 @@
+# coding: utf-8
+
+class Solution:
+    """
+    @param: : the given number
+    @return: whether whether there're two integers
+    """
+    def checkSumOfSquareNumbers(self, num):
+        # write your code here
+        if num < 0:
+            return False
+        import math
+        upper = int(math.sqrt(num))
+        for i in range(upper + 1):
+            start, end = i, upper # 二分法的干活
+            while start <= end:
+                j = int((start + end) / 2)
+                s = i * i + j * j
+                if s == num:
+                    return True
+                elif s > num:
+                    end = j - 1
+                else:
+                    start = j + 1
+        return False
+        
+# easy: http://lintcode.com/zh-cn/problem/check-sum-of-square-numbers/
