This article is participating in Python Theme Month. See the link for details

describe

A square triple (a,b,c) is a triple where a, b, and c are integers and a^2 + b^2 = c^2.

Given an integer n, return the number of square triples such that 1 <= a, b, c <= n.

Example 1:

Input: n = 5
Output: 2
Explanation: The square triples are (3,4,5) and (4,3,5).
Copy the code

Example 2:

Input: n = 10
Output: 4
Explanation: The square triples are (3,4,5), (4,3,5), (6,8,10), and (8,6,10).
Copy the code

Note:

1 <= n <= 250
Copy the code

parsing

A ^2 + b^2 = c^2 [1,n] a^2 + b^2 = c^2

  • So if we’re looking for a right triangle, if we’re looking for a right triangle, if we’re looking for a right triangle, if we’re looking for a right triangle, if we’re looking for a right triangle, we’re looking for a right triangle
  • After finding all (a,b,c) that satisfy the problem,c is the largest, so its position cannot be moved, but it can switch between a and B, so the final triple is twice as many as the existing triple

This is a more violent solution, which simply uses three traversals to find all the final triples.

answer

class Solution(object):
    def countTriples(self, n):
        """
        :type n: int
        :rtype: int
        """
        result = 0
        for i in range(1,n+1):
            for j in range(i+1,n+1):
                for k in range(j+1,n+1):
                    if i+j>k and i*i + j*j == k*k:
                        result += 1
        return result*2
        	      
		
Copy the code

The results

Each node in the Python online submission list has linked to the node. Memory Usage: 10000 ms Submissions in Python online submissions for Count Square Sum Triples.Copy the code

parsing

In addition, we can first store all the square results from 1 to n into the set S, and then use the existing combination permutation function to arrange all the values in S and combine the combination P with the growth degree of 2, and then traverse whether the sum of elements in each combination p exists in S. If so, the counter C is increased by one. After traversal, return c*2 as the result.

answer

class Solution(object):
    def countTriples(self, n):
        """
        :type n: int
        :rtype: int
        """
        s=set()
        for i in range(1,n+1):
            s.add(i*i)
        p=combinations(s,2)
        c=0
        for i in p:
            if(sum(list(i)) in s):
                c=c+1
        return c*2
Copy the code

The results

Given in the linked list. Memory Usage: 10000 ms Submissions in Python online submissions for Count Square Sum Triples.Copy the code

parsing

There are other solutions, but the basic principle is the same, the only difference is the code form, see the official website solution for details.

Original link: leetcode.com/problems/co…

Your support is my biggest motivation